Encode and Decode Strings

A message queue can only carry a single string per message, but your service needs to send whole lists of strings. Design the format yourself: write a pair of functions

def encode(strs: list[str]) -> str
def decode(s: str) -> list[str]

so that decode(encode(strs)) == strs for every list of strings.

• The strings may contain any character at all: letters, digits, spaces, punctuation, newlines, "\0", emoji. No character is "safe" to use as a separator on its own.
• Empty strings are allowed, and [], [""] and ["", ""] must all come back as they went in.
• decode receives only the encoded string: it must not depend on anything remembered from earlier encode calls (the tests reload your module between the two).
• Build the format by hand: no json, pickle, repr/eval, base64 or similar helpers.

decode(encode(["hello", "world"]))     # ["hello", "world"]
decode(encode(["a,b", "", "7:x#"]))    # ["a,b", "", "7:x#"]
decode(encode([]))                     # []
decode(encode([""]))                   # [""]

Constraints: up to 200,000 strings with a total length of up to 2,000,000 characters. Both functions should run in O(total length). In particular, decode must not repeatedly slice off the front of the remaining text (s = s[k:]), since every slice copies the rest of the string.