Encode and Decode Strings

This problem looks easy until you hit the trap. You have a list of strings. You must squash them into one single string. Then you must split that single string back into the exact same list. The trap is that the strings can contain any character. So you cannot just glue them with a comma and hope.

🎯 The Problem

You squash a list of strings into one string, then split it back into the exact same list.

• Turning the list into one string is called encoding. Encoding means packing data into a single form you can send or store.
• Turning that one string back into the list is called decoding.
• The strings can contain anything. Commas. Spaces. Even the # mark.
• So your method must work for any character inside the words.

For ["hello", "world"]: you encode it into one string, then decode that string back to ["hello", "world"], exactly.

Input:  ["hello", "world"]
Encoded: "5#hello5#world"
Output:  ["hello", "world"]

Explanation: Each word is stored as its length, a # mark, then the word.

Here is the problem drawn out. We squash the list into one string, then pull it back apart.

🐢 Approach 1: Join With a Separator (Brute Force)

The idea in one line: glue the words with a marker character, then split on it.

The idea:

• A separator is a marker you put between items so you know where one ends.
• Like a comma. So ["hello", "world"] becomes "hello,world".
• To decode, split on the comma.

Why it is weak:

• A word can contain the separator itself.
• Say the list is ["a,b", "c"]. You glue it into "a,b,c". Splitting gives three pieces, not two. The data is broken.
• A rarer separator does not help. Strings can hold any character, so no single separator is ever safe.

Here is the separator-based code for that idea:

class Codec:
    def encode(self, strs):
        return "#".join(strs)

    def decode(self, s):
        return s.split("#")

⚡ Approach 2: Length-Prefix Encoding (Best)

The idea in one line: write each word’s length before the word, so the decoder reads by count, not by searching.

The idea:

• This is length-prefix encoding. It stores the size of each piece right before the piece.
• Before each word, write its length, then a #, then the word.
• So "hello" becomes "5#hello" and "world" becomes "5#world". Glued: "5#hello5#world".

How decode works:

• Read digits until you hit the #. Those digits are the length.
• Read exactly that many characters after the #. That is one word.
• Jump to the next position and repeat until the string is used up.

Why it never breaks:

• The decoder never searches for a marker inside the word.
• It reads the count, then grabs exactly that many characters and stops.
• A # or comma inside the word cannot fool it. The length gave the exact size.

Here is the decode dry run on "5#hello5#world".

Steps to Solve

1. To encode, start with an empty result string.
2. For each word, append its length, then a #, then the word itself.
3. Return the joined result.
4. To decode, start at position zero with an empty list.
5. Read characters as digits until you reach a #. Those digits form the length number.
6. Move one step past the #, then read exactly that many characters as the next word.
7. Add the word to the list and move the position forward.
8. Repeat until you reach the end of the string, then return the list.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// pack all words into one string using length#word
void encode(char *words[], int n, char *out) {
    out[0] = '\0';
    char buf[32];
    for (int i = 0; i < n; i++) {
        sprintf(buf, "%d#", (int)strlen(words[i]));  // length then #
        strcat(out, buf);
        strcat(out, words[i]);                       // then the word
    }
}

int main(void) {
    char *words[] = {"hello", "world"};
    char encoded[128];
    encode(words, 2, encoded);
    printf("%s\n", encoded);

    // decode by reading length, then that many characters
    int pos = 0;
    int len = (int)strlen(encoded);
    while (pos < len) {
        int num = 0;
        while (encoded[pos] != '#') {        // read the digits
            num = num * 10 + (encoded[pos] - '0');
            pos++;
        }
        pos++;                               // skip the #
        char word[64];
        strncpy(word, encoded + pos, num);   // read exactly num chars
        word[num] = '\0';
        pos += num;
        printf("%s\n", word);
    }
    return 0;
}

5#hello5#world
hello
world

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string encode(const vector<string>& words) {
    string out;
    for (const string& w : words) {
        out += to_string(w.size()) + "#" + w;  // length#word
    }
    return out;
}

vector<string> decode(const string& s) {
    vector<string> result;
    int pos = 0;
    while (pos < (int)s.size()) {
        int num = 0;
        while (s[pos] != '#') {              // read the digits
            num = num * 10 + (s[pos] - '0');
            pos++;
        }
        pos++;                               // skip the #
        result.push_back(s.substr(pos, num)); // read exactly num chars
        pos += num;
    }
    return result;
}

int main() {
    vector<string> words = {"hello", "world"};
    string encoded = encode(words);
    cout << encoded << endl;
    vector<string> decoded = decode(encoded);
    for (const string& w : decoded) {
        cout << w << endl;
    }
    return 0;
}

5#hello5#world
hello
world

import java.util.ArrayList;
import java.util.List;

public class EncodeDecode {
    static String encode(List<String> words) {
        StringBuilder sb = new StringBuilder();
        for (String w : words) {
            sb.append(w.length()).append('#').append(w);  // length#word
        }
        return sb.toString();
    }

    static List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        int pos = 0;
        while (pos < s.length()) {
            int num = 0;
            while (s.charAt(pos) != '#') {        // read the digits
                num = num * 10 + (s.charAt(pos) - '0');
                pos++;
            }
            pos++;                                // skip the #
            result.add(s.substring(pos, pos + num)); // read exactly num chars
            pos += num;
        }
        return result;
    }

    public static void main(String[] args) {
        List<String> words = new ArrayList<>();
        words.add("hello");
        words.add("world");
        String encoded = encode(words);
        System.out.println(encoded);
        for (String w : decode(encoded)) {
            System.out.println(w);
        }
    }
}

5#hello5#world
hello
world

def encode(words):
    result = ""
    for w in words:
        result += str(len(w)) + "#" + w   # length#word
    return result


def decode(s):
    result = []
    i = 0
    while i < len(s):
        j = i
        while s[j] != "#":        # read the digits of the length
            j += 1
        length = int(s[i:j])      # the number before the #
        word = s[j + 1:j + 1 + length]  # read exactly that many chars
        result.append(word)
        i = j + 1 + length        # jump to the next word
    return result


words = ["hello", "world"]
encoded = encode(words)
print(encoded)
print(decode(encoded))

5#hello5#world
['hello', 'world']

function encode(words) {
  let result = "";
  for (const w of words) {
    result += w.length + "#" + w; // length#word
  }
  return result;
}

function decode(s) {
  const result = [];
  let i = 0;
  while (i < s.length) {
    let j = i;
    while (s[j] !== "#") {       // read the digits of the length
      j++;
    }
    const length = parseInt(s.slice(i, j), 10); // the number before the #
    const word = s.slice(j + 1, j + 1 + length); // read exactly that many chars
    result.push(word);
    i = j + 1 + length;          // jump to the next word
  }
  return result;
}

const words = ["hello", "world"];
const encoded = encode(words);
console.log(encoded);
console.log(decode(encoded));

5#hello5#world
[ 'hello', 'world' ]

Let us read the Python version line by line. The decode part is the one interviewers probe.

In encode we start with an empty result. For each word we add three things: the length as text, a #, then the word. So "hello" becomes "5#hello". We return the joined string.

In decode we start with an empty result list and an index i at zero. The outer while runs until i reaches the end of the string.

Inside, we set j = i. Then the inner while s[j] != "#" moves j forward until it lands on the #. So now everything between i and j is the length written as digits.

The line length = int(s[i:j]) turns those digits into a real number. This is the size of the next word.

The line word = s[j + 1:j + 1 + length] is the heart of it. We skip past the # with j + 1. Then we read exactly length characters. Because we trust the length, we never guess where the word ends. We know its exact size. So a # inside the word cannot fool us.

We append the word. Then i = j + 1 + length jumps the index to the start of the next chunk. We loop again until the whole string is read.

This is why length-prefix encoding is safe for any character. The decoder reads by count, not by searching for a marker.

⏱️ Time and Space Complexity

Both encode and decode walk through every character once. So both run in O(total characters) time. The encoded string holds all the words plus a small length tag for each, so the extra space is also linear in the input size. The naive separator way looks the same on speed but it is simply wrong, so it does not belong in the comparison of correct methods.

🧩 Key Takeaways

• ✅ A single separator like a comma fails because the data can contain that same character.
• ✅ Length-prefix encoding stores each word as its length, a #, then the word.
• ✅ The decoder reads the length first, then grabs exactly that many characters.
• ✅ Because we read by count, any character inside a word is safe, even #.
• ✅ Both encode and decode run in linear time over the total characters.

🚀 What’s Next?

• Isomorphic Strings
• Palindromic Substrings