Encode and Decode Strings

MEDIUM✓ CHIP-TIMEDLC #271 — FULL STATEMENT ↗

The drill: Pack a list of strings — any characters allowed, including empty strings — into a single string, then unpack it back into the exact original list. No delimiter can be assumed absent from the data itself. Judged here via a roundTrip wrapper: decode(encode(x)) must reproduce x exactly.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A list of strings — any characters allowed, including empty strings — needs packing into a single string, and that single string needs to unpack back into the exact original list.

No character or substring can be assumed missing from the data, so a naive separator like a comma can't be trusted to always mean 'boundary' rather than 'content'.

This site verifies the drill as a round trip: your encode and decode are chained together, and the list that comes out the far end must match the list that went in, element for element, in the same order.

EX 01

strs = ["race", "pace", "grind"]

→ ["race", "pace", "grind"]

PLAIN WORDS, NO SPECIAL CHARACTERS

EX 02

strs = []

→ []

EMPTY LIST OF STRINGS

EX 03

strs = [""]

→ [""]

SINGLE EMPTY STRING

the list can hold any number of strings, including zero strings
individual strings may contain any characters, including the empty string
the reconstructed list must match the original exactly, order included
judged as a round trip: decode(encode(list)) must equal list

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Joining strings with a comma looks done in one line, until a string itself contains a comma — decoding then can't tell a real separator from data. What information would let you split unambiguously no matter what's inside the strings?

HINT 2 THE STRUCTURE

If every string announces its own length before it starts, you never need to search for a separator at all — you just count characters forward from wherever you already are.

HINT 3 ONE STEP FROM THE ANSWER

Encode each string as its length, a marker character, then the raw string itself. Decode by reading digits up to the marker, taking exactly that many characters as the word, then repeating from where you left off.

COACH'S BOARD — THE PATTERN, STEP BY STEP

LENGTH BEFORE MARKERPATTERN · LENGTH-PREFIXED CHUNKSstrs = ["race", "pace", "grind"]

race

pace

grind

PAYLOAD

— empty —

STEP 1

strs = [race, pace, grind]. Encode by prefixing each word with its length and a # marker.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/encode-and-decode-strings.py — RACE PACE

LANG ▸

PACE ▸

class Codec:
    def encode(self, strs: List[str]) -> str:
        parts = []
        for s in strs:
            parts.append(f"{len(s)}#{s}")
        return "".join(parts)

    def decode(self, s: str) -> List[str]:
        result = []
        i = 0
        n = len(s)
        while i < n:
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i:j])
            result.append(s[j + 1 : j + 1 + length])
            i = j + 1 + length
        return result


class Solution:
    def roundTrip(self, strs: List[str]) -> List[str]:
        codec = Codec()
        return codec.decode(codec.encode(strs))

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 25 LN

class Codec:
    def encode(self, strs: List[str]) -> str:
        parts = []
        for s in strs:
            escaped = s.replace("\\", "\\\\").replace(",", "\\,")
            parts.append(escaped + ",")
        return "".join(parts)

    def decode(self, s: str) -> List[str]:
        result = []
        current = []
        i = 0
        n = len(s)
        while i < n:
            c = s[i]
            if c == "\\" and i + 1 < n:
                current.append(s[i + 1])
                i += 2
            elif c == ",":
                result.append("".join(current))
                current = []
                i += 1
            else:
                current.append(c)
                i += 1
        return result


class Solution:
    def roundTrip(self, strs: List[str]) -> List[str]:
        codec = Codec()
        return codec.decode(codec.encode(strs))

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 32 LN

class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s.length()).append('#').append(s);
        }
        return sb.toString();
    }

    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        int i = 0;
        int n = s.length();
        while (i < n) {
            int j = i;
            while (s.charAt(j) != '#') {
                j++;
            }
            int length = Integer.parseInt(s.substring(i, j));
            result.add(s.substring(j + 1, j + 1 + length));
            i = j + 1 + length;
        }
        return result;
    }
}

class Solution {
    public String[] roundTrip(String[] strs) {
        Codec codec = new Codec();
        List<String> decoded = codec.decode(codec.encode(Arrays.asList(strs)));
        return decoded.toArray(new String[0]);
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 33 LN

class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            String escaped = s.replace("\\", "\\\\").replace(",", "\\,");
            sb.append(escaped).append(',');
        }
        return sb.toString();
    }

    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        StringBuilder current = new StringBuilder();
        int i = 0;
        int n = s.length();
        while (i < n) {
            char c = s.charAt(i);
            if (c == '\\' && i + 1 < n) {
                current.append(s.charAt(i + 1));
                i += 2;
            } else if (c == ',') {
                result.add(current.toString());
                current.setLength(0);
                i++;
            } else {
                current.append(c);
                i++;
            }
        }
        return result;
    }
}

class Solution {
    public String[] roundTrip(String[] strs) {
        Codec codec = new Codec();
        List<String> decoded = codec.decode(codec.encode(Arrays.asList(strs)));
        return decoded.toArray(new String[0]);
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 40 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED