Encode and Decode Strings

1. Problem & Core Objective

The problem

Design an algorithm to encode a list of strings into a single string, and decode that single string back into the original list.

String  encode(List<String> strs);
List<String> decode(String s);

The encoded string is sent over a network; your decode must recover the original list exactly.

Input:  ["neet","code","love","you"]
encode -> some single string
decode -> ["neet","code","love","you"]     // must round-trip exactly

Constraints:

• 0 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] contains any possible characters out of 256 valid ASCII characters

What the interviewer is actually testing

This is a design question disguised as a string question. There's no clever algorithm — the entire assessment is whether you can reason about an encoding format and defend it against adversarial input.

1. Do you immediately reach for a delimiter, then realize it's broken? Almost everyone's first instinct is "join with a comma". The interviewer is waiting to see whether you find the flaw, or whether they have to point it out.
2. Can you design a self-delimiting format? The fix — length-prefixing — is a genuine idea from real serialization protocols.
3. Do you handle the nasty cases? Empty strings, empty lists, strings containing your delimiter, strings containing digits.
4. Can you argue correctness? "Why can't this break?" is the whole follow-up.

The constraint line "any possible characters" is the problem. It is telling you that no character is safe to use as a separator.

2. First-Principles Thought Process

Step 1 — Try the obvious thing and break it

First instinct: join with a delimiter.

String.join(",", strs);              // "neet,code,love,you"
s.split(",");                        // back again

Now attack it. What if a string contains a comma?

Input:   ["a,b", "c"]
Encoded: "a,b,c"
Decoded: ["a", "b", "c"]        ✗ three strings, not two

Information is destroyed. The decoder cannot tell a separator comma from a data comma.

And the constraints explicitly say any ASCII character may appear — so there is no "safe" character to pick instead. Not #, not \0, not |. Any choice can appear in the payload.

Step 2 — Consider escaping, and weigh it

The standard fix in real formats (CSV, JSON) is escaping: pick a delimiter, and prefix any occurrence in the data with an escape character.

"a,b"  ->  "a\,b"

This works, but it brings problems:

• You must also escape the escape character (\ → \\), or you get the same ambiguity one level down.
• Decoding requires character-by-character scanning with state.
• The output can double in size in the worst case.

It's correct but fiddly. Is there something simpler?

Step 3 — The reframe that solves it

The delimiter approach fails because the decoder must search for a boundary — and any character it searches for might be data.

So flip it:

What if the decoder never has to search? What if it's told, in advance, exactly how many characters to take?

If each string is preceded by its length, the decoder reads the number, then consumes exactly that many characters blindly. It never inspects them, so their content is irrelevant. A comma, a #, a newline — all just data.

That is length-prefixing, and it's how real protocols do it: HTTP's Content-Length, Redis's RESP, Protocol Buffers' varint-prefixed fields.

Step 4 — Make the length itself unambiguous

One problem remains. If you write:

4neet4code

how does the decoder know the length is 4 and not 4 followed by… wait. What about a string of length 12? "12abcdefghijkl" — is the length 1, 12, or 12a? The digits of the length run into the payload.

You need a terminator for the length field. A non-digit character works, because a length is always digits:

4#neet4#code4#love3#you

The decoder reads digits until it hits #, and that's the length. A # inside the payload is harmless, because the decoder only scans for # when it's expecting a length — and once it has the length, it consumes blindly.

That asymmetry is the entire insight.

3. Solution Paths

Approach 1 — Naive delimiter (broken)

public String encode(List<String> strs) {
    return String.join(",", strs);
}
public List<String> decode(String s) {
    return Arrays.asList(s.split(","));
}

Broken. Fails on any string containing a comma, and on empty strings (split discards trailing empties). Present it only to motivate the real answer — and name the counterexample yourself.

Counter-questions on this approach

⭐ "Show me an input that breaks this."

["a,b", "c"] encodes to "a,b,c" and decodes to three strings instead of two — the decoder can't distinguish a separator comma from a data comma. And the constraints say any ASCII character may appear, so there is no "safe" character I could pick instead.

"Is there a second, separate bug here?"

Yes. String.split discards trailing empty strings, so ["a", ""] loses its second element entirely. Even ignoring the delimiter collision, this fails on empty strings.

Approach 2 — Escaping

public String encode(List<String> strs) {
    StringBuilder sb = new StringBuilder();
    for (String s : strs) {
        for (char c : s.toCharArray()) {
            if (c == '\\' || c == ',') sb.append('\\');   // escape the escape, and the delimiter
            sb.append(c);
        }
        sb.append(',');                                   // unescaped comma = a real separator
    }
    return sb.toString();
}

public List<String> decode(String s) {
    List<String> res = new ArrayList<>();
    StringBuilder cur = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '\\') {
            cur.append(s.charAt(++i));      // the NEXT character is literal data
        } else if (c == ',') {
            res.add(cur.toString());        // unescaped comma ends this string
            cur.setLength(0);
        } else {
            cur.append(c);
        }
    }
    return res;
}

• Time: O(N) both ways, where N is total characters.
• Space: O(N), but the encoded form can be up to 2× the input if every character needs escaping.

Correct, and worth knowing because it's how CSV and JSON actually work. But it's more code, more state, and easier to get wrong than the alternative.

Counter-questions on this approach

⭐ "This is correct — it's what CSV and JSON do. Why not stop here?"

It is correct. Three reasons to prefer length-prefixing: decoding must examine every character to spot escapes, whereas length-prefixing consumes the payload blindly; worst-case output doubles if every character needs escaping, versus a fixed ~4 characters per string; and it carries decode state (am I inside an escape?) that's easy to get wrong. I'd choose escaping only if the format had to stay human-readable and greppable.

"What if you escape the delimiter but forget to escape the escape character?"

The ambiguity just moves down one level. A payload ending in a literal \ would produce "a\,", and the decoder can't tell whether that comma is escaped data or a real separator. Escaping the escape is not optional.

Approach 3 — Length prefixing (optimal)

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> res = new ArrayList<>();
    int i = 0;

    while (i < s.length()) {
        int j = i;
        while (s.charAt(j) != '#') j++;              // scan the length digits

        int len = Integer.parseInt(s.substring(i, j));
        res.add(s.substring(j + 1, j + 1 + len));    // take EXACTLY len characters

        i = j + 1 + len;                             // jump past this entry entirely
    }
    return res;
}

How it works. Each entry is <length>#<payload>. Decoding is a loop: scan forward to the # to read the length, take exactly that many characters as the payload, then jump past both.

Trace encoding ["neet","code","love","you"]:

Encoded: "4#neet4#code4#love3#you"

Trace decoding it:

i == 23 == s.length() → done. Result matches. ✓

The adversarial case — a string containing # and digits:

Input:   ["4#hello", "x"]
Encoded: "7#4#hello1#x"

Decoding: at i=0, scan to the first # at index 1 → length 7. Take exactly 7 characters starting at index 2: "4#hello". ✓ The embedded # and digits were consumed blindly as payload. Then i = 9, scan to # at 10 → length 1 → take "x". ✓

This is the case to demonstrate unprompted. It's the entire justification for the design.

• Time: O(N) to encode, O(N) to decode.
• Space: O(N) for the output. Overhead is only a few characters per string (the digits plus #), versus escaping's potential doubling.

Counter-questions on this approach

⭐ "What if one of the strings contains your # separator?"

Completely harmless, and that's the whole design. The decoder only scans for # when it is expecting a length — and lengths are pure digits, so the first # is always the genuine terminator. Once it has the length it consumes exactly that many characters without inspecting them. Demonstration: ["4#hello", "x"] encodes to "7#4#hello1#x"; decoding reads length 7 and lifts "4#hello" out verbatim.

⭐ "Can you break your own encoding?"

Not with anything my encoder produced — the parse is deterministic and never depends on payload content. It can be broken by malformed input that didn't come from my encoder: a declared length longer than the remaining characters would throw. For untrusted input I'd bounds-check the scan and validate each length against what's left.

"Why do you need the # at all? Why not just write the length and then the string?"

Because the length's digits would run into the payload. "12abc" is ambiguous — is the length 1, 12, or 12a? A non-digit terminator resolves it, since a length is always digits.

"substring copies in Java. Doesn't that make decoding worse than O(N)?"

No. Each character of the input ends up in exactly one output string, so the total copying across the whole decode is O(N). It would be a problem only if the substrings overlapped.

Approach 4 — Fixed-width length prefix

Since strings are at most 200 characters, a fixed 3-digit length removes the # entirely:

sb.append(String.format("%03d", s.length())).append(s);    // "004neet"
// decode: read 3 chars as the length, then that many as the payload

Simpler decoding (no scanning at all), but it hard-codes a maximum length. Mention it as a variant when the bound is known — it's what fixed-format binary protocols do.

Counter-questions on this approach

⭐ "This removes the # and the scan entirely. Why isn't it your default?"

Because it hard-codes a maximum string length — three digits caps payloads at 999 characters. That's fine given this problem's bound of 200, and it's exactly what fixed-format binary protocols do. But as a general design it trades away flexibility, and the variable-width version costs almost nothing.

Comparison

4. Why the Optimal Wins

Against the plain delimiter. It's not a performance comparison — the delimiter version is simply wrong. Any payload containing the separator destroys the boundary information. With "any ASCII character" allowed, no separator is safe.

Against escaping. Both are correct. Length-prefixing wins on three counts:

• Decoding requires no scanning of the payload. Once the length is known, you substring in one step. Escaping must examine every character to spot escapes.
• Bounded overhead. Length-prefixing adds ~4 characters per string; escaping can double the entire payload.
• Less state. No escape-character tracking, no "is this escape escaped?" edge case.

The correctness argument — this is what to say when asked "can this break?":

"The decoder is only ever in one of two modes. Either it's reading a length, in which case it scans for the first # — and lengths are pure digits, so the first # is always the real terminator. Or it's reading a payload, in which case it consumes a pre-determined number of characters without inspecting them at all.

Since the payload is never searched, its contents can't be misinterpreted. There's no character the user can supply that changes the parse."

That's a genuine correctness argument rather than "I tested it and it worked".

Why O(N) is the floor. You must read every character to encode it and write every character to decode it. Both directions are optimal.

5. Java Prerequisites

StringBuilder for building the encoded string

StringBuilder sb = new StringBuilder();
sb.append(s.length()).append('#').append(s);
return sb.toString();

append is overloaded for every type — int, char, String — so s.length() needs no manual conversion.

Never use += in the loop. Strings are immutable, so result += s copies everything each time — O(N²). See 02 §9.

substring bounds

s.substring(i, j);          // [i, j) — START inclusive, END exclusive
s.substring(j + 1, j + 1 + len);

Getting substring(start, start + len) right is the whole decoder. Reading it as "start here, take len characters" keeps the arithmetic straight.

substring is O(len) in Java 7+ — it copies. Fine here since each character is copied exactly once overall.

Integer.parseInt

int len = Integer.parseInt(s.substring(i, j));

Throws NumberFormatException on non-digits or an empty string. Here it can't fire, because i..j is guaranteed to be the digits written by encode — but say that you know why it's safe.

charAt in the scan loop

while (s.charAt(j) != '#') j++;

No bounds check is needed given well-formed input, because encode always writes a #. For defensive code you'd add j < s.length(). Worth mentioning: "I'm trusting the input came from my own encoder; for untrusted input I'd bounds-check."

Empty strings and empty lists

encode(List.of());            // ""        — the while loop never runs on decode
encode(List.of(""));          // "0#"      — length 0, then zero characters

s.substring(j+1, j+1+0) returns "" — Java allows a zero-width substring. Both cases work with no special handling, which is a point in the design's favour.

6. Interview Communication Guide

Clarifying questions

1. "What characters can appear in the strings?" — the question. "Any ASCII" is what kills the delimiter approach.
2. "Can strings be empty? Can the list be empty?" — both must round-trip.
3. "Is there a maximum string length?" — if bounded, the fixed-width variant becomes available.
4. "Does the encoded form need to be human-readable, or compact?" — decides between text and binary framing.
5. "Can I assume decode only ever receives output from my encode?" — decides how much validation to write.

The pitch

"My first instinct is to join with a delimiter like a comma. But that breaks immediately: if a string contains a comma, the decoder splits in the wrong place. And the constraints say any ASCII character can appear, so there's no safe delimiter to pick.

I could escape the delimiter, like CSV does — that works, but it needs escape-the-escape handling and can double the output size.

Better: length-prefix each string. I write the length, a #, then the string. Decoding reads digits up to the # to get the length, then takes exactly that many characters without looking at them.

That's why it's safe — the payload is never searched, so nothing in it can be misinterpreted. A # inside a string is just data. Let me show you: ["4#hello", "x"] encodes to 7#4#hello1#x, and decoding takes 7 characters after the first #, recovering 4#hello exactly.

O(N) both ways, with about four characters of overhead per string."

Edge cases to raise proactively

["#"] and ["4#hello"] are the two to volunteer. They're the cases the naive solution fails, and demonstrating them proves the design rather than asserting it.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

⭐ "What if the strings could be gigantic — gigabytes each?"

The length prefix still works, but substring copies. I'd stream instead: read the length, then copy exactly that many bytes through a buffer rather than materializing the whole string. This is exactly how HTTP Content-Length framing works.

⭐ "What if you're encoding bytes, not text?"

Use a fixed-width binary length — say 4 bytes big-endian — followed by the raw payload. No # needed, no digit parsing. That's Protocol Buffers' and RESP's approach, and it avoids the text-encoding question entirely.

"How would you make it resilient to corruption?"

Add a checksum per entry, and/or a magic byte at the start of each record so a decoder can resynchronize after damage. Pure length-prefixing has no recovery: one wrong length and everything after it misparses. Worth stating as a genuine limitation of the design.

"What if strings could contain the null character or newlines?"

No change at all. That's the point of the design — the payload is never inspected. This is also why it beats any line-based format.