Encode and Decode Strings problem and solution in Java and Python

This is a classic interview problem often seen in FAANG rounds. Let’s go step-by-step 👇

---

🧩 Problem: Encode and Decode Strings

Problem Statement

You are given an array of strings. You need to encode them into a single string so that they can be easily decoded back into the original array.

The key is to design an algorithm that works even when strings contain special characters, spaces, or numbers.

---

Example

Input:

["hello", "world"]

Encoded Output:

"5#hello5#world"

Decoded Output:

["hello", "world"]

---

💡 Intuition

We can’t just use a simple separator like , or | because what if one of the strings contains that character?

So we prefix each string with its length and a delimiter (for example, #) — this way, we always know exactly how many characters to read next.

---

🧠 Approach

Encoding

1. For each string, calculate its length.
2. Append length + '#' + string to the result.

Decoding

1. Start reading from the beginning.
2. Read characters until you reach # — that gives the length of the next string.
3. Read exactly that many characters to get the string.
4. Repeat until the end.

---

💻 Java Solution

import java.util.*;

class Codec {
    // Encode a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s.length()).append('#').append(s);
        }
        return sb.toString();
    }

    // Decode a single string to a list of strings.
    public List<String> decode(String str) {
        List<String> result = new ArrayList<>();
        int i = 0;
        while (i < str.length()) {
            int j = i;
            while (str.charAt(j) != '#') {
                j++;
            }
            int length = Integer.parseInt(str.substring(i, j));
            j++; // skip '#'
            String word = str.substring(j, j + length);
            result.add(word);
            i = j + length;
        }
        return result;
    }

    public static void main(String[] args) {
        Codec codec = new Codec();
        List<String> input = Arrays.asList("hello", "world", "foo#bar", "123");
        String encoded = codec.encode(input);
        System.out.println("Encoded: " + encoded);
        System.out.println("Decoded: " + codec.decode(encoded));
    }
}

---

🐍 Python Solution

class Codec:
    def encode(self, strs):
        return ''.join(f"{len(s)}#{s}" for s in strs)

    def decode(self, s):
        res, i = [], 0
        while i < len(s):
            j = i
            while s[j] != '#':
                j += 1
            length = int(s[i:j])
            j += 1
            res.append(s[j:j + length])
            i = j + length
        return res


# Example usage
codec = Codec()
encoded = codec.encode(["hello", "world", "foo#bar", "123"])
print("Encoded:", encoded)
print("Decoded:", codec.decode(encoded))

---

⏱️ Complexity

Operation	Time Complexity	Space Complexity
Encoding	O(N)	O(1)
Decoding	O(N)	O(N)

Where N is the total number of characters across all strings.

---

🧠 Real-world Analogy

This is similar to how network protocols encode data before sending over the wire — they add metadata like length before each message so the receiver knows where one message ends and the next begins.

---