Encode and Decode Strings

medium
Arrays & HashingStringDesign

Design an algorithm to encode a list of strings into a single string, and decode that single string back into the original list of strings. The encoded string should be transmittable over a network and decodable without ambiguity.

Implement the encode function that takes a list of strings and returns a single encoded string, and the decode function that takes the encoded string and returns the original list of strings.

The algorithm must handle any valid string characters, including delimiters, special characters, and empty strings.

Examples

Example 1

  • Input: strs = ["hello","world"]
  • Output: ["hello","world"]
  • Explanation: The encoded string can be any representation, as long as decode(encode(strs)) returns the original list.

Example 2

  • Input: strs = [""]
  • Output: [""]
  • Explanation: The list contains one empty string. Encoding and decoding must preserve it.

Example 3

  • Input: strs = ["we","say",":","yes","!@#$%^&*()"]
  • Output: ["we","say",":","yes","!@#$%^&*()"]
  • Explanation: Special characters and delimiters must be handled correctly.

Constraints

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] contains any possible characters including Unicode.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Length Prefix Encoding

Intuition

The most robust way to encode strings is to prefix each string with its length followed by a delimiter. For each string, we write the length as a number, then a special character like #, then the string itself. During decoding, we read the length, skip past the #, and extract exactly that many characters. This approach is unambiguous because we always know exactly how many characters to read, regardless of what those characters are.

Algorithm

  1. **Encode:** For each string, append its length, a `#` delimiter, and the string itself to the result.
  2. **Decode:** Initialize an index `i` at 0. While `i` is less than the encoded string length:
  3. Return the decoded list.
TimeO(n) where n is the total number of characters across all stringsSpaceO(n) for the encoded/decoded output

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    string encode(vector<string>& strs) {
        string result;
        for (const string& s : strs) {
            result += to_string(s.size()) + "#" + s;
        }
        return result;
    }

    vector<string> decode(string s) {
        vector<string> result;
        int i = 0;
        while (i < s.size()) {
            int j = s.find('#', i);
            int len = stoi(s.substr(i, j - i));
            result.push_back(s.substr(j + 1, len));
            i = j + 1 + len;
        }
        return result;
    }
};
Java 21
class Solution {
    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;
        while (i < s.length()) {
            int j = s.indexOf('#', i);
            int len = Integer.parseInt(s.substring(i, j));
            result.add(s.substring(j + 1, j + 1 + len));
            i = j + 1 + len;
        }
        return result;
    }
}
Python 3.12
from typing import List


class Solution:
    def encode(self, strs: List[str]) -> str:
        result = []
        for s in strs:
            result.append(str(len(s)) + "#" + s)
        return "".join(result)

    def decode(self, s: str) -> List[str]:
        result = []
        i = 0
        while i < len(s):
            j = s.index("#", i)
            length = int(s[i:j])
            result.append(s[j + 1:j + 1 + length])
            i = j + 1 + length
        return result
Go 1.26
import (
    "strconv"
    "strings"
)

func encode(strs []string) string {
    var sb strings.Builder
    for _, s := range strs {
        sb.WriteString(strconv.Itoa(len(s)))
        sb.WriteByte('#')
        sb.WriteString(s)
    }
    return sb.String()
}

func decode(s string) []string {
    result := []string{}
    i := 0
    for i < len(s) {
        j := strings.Index(s[i:], "#") + i
        length, _ := strconv.Atoi(s[i:j])
        result = append(result, s[j+1:j+1+length])
        i = j + 1 + length
    }
    return result
}
Approach 2

Escaping Delimiter

Intuition

An alternative approach uses a delimiter to separate strings, but escapes any occurrence of the delimiter within the strings themselves. We choose a delimiter (e.g., /) and an escape character (e.g., :). Before joining, we escape any existing escape characters by doubling them, then escape the delimiter. During decoding, we reverse the escaping process. This is similar to how CSV and other text formats handle special characters.

Algorithm

  1. **Encode:** For each string, replace all `:` with `::` (escape the escape character), then replace all `/` with `:/` (escape the delimiter). Join all escaped strings with `/`.
  2. **Decode:** Split the encoded string by unescaped `/` characters. For each part, reverse the escaping: replace `:/` with `/`, then replace `::` with `:`.
  3. Return the decoded list.
TimeO(n) where n is the total number of characters across all stringsSpaceO(n) for the encoded/decoded output

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    string encode(vector<string>& strs) {
        string result;
        for (int i = 0; i < strs.size(); i++) {
            string escaped;
            for (char c : strs[i]) {
                if (c == ':') escaped += "::";
                else if (c == '/') escaped += ":/";
                else escaped += c;
            }
            if (i > 0) result += "/";
            result += escaped;
        }
        // Prefix with count to handle empty list vs list with one empty string
        return to_string(strs.size()) + "#" + result;
    }

    vector<string> decode(string s) {
        int j = s.find('#');
        int count = stoi(s.substr(0, j));
        if (count == 0) return {};

        string encoded = s.substr(j + 1);
        vector<string> result;
        string current;

        int i = 0;
        while (i < encoded.size()) {
            if (encoded[i] == ':' && i + 1 < encoded.size()) {
                if (encoded[i + 1] == ':') {
                    current += ':';
                    i += 2;
                } else if (encoded[i + 1] == '/') {
                    current += '/';
                    i += 2;
                } else {
                    current += encoded[i];
                    i++;
                }
            } else if (encoded[i] == '/') {
                result.push_back(current);
                current.clear();
                i++;
            } else {
                current += encoded[i];
                i++;
            }
        }
        result.push_back(current);
        return result;
    }
};
Java 21
class Solution {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        sb.append(strs.size()).append('#');
        for (int k = 0; k < strs.size(); k++) {
            if (k > 0) sb.append('/');
            for (char c : strs.get(k).toCharArray()) {
                if (c == ':') sb.append("::");
                else if (c == '/') sb.append(":/");
                else sb.append(c);
            }
        }
        return sb.toString();
    }

    public List<String> decode(String s) {
        int j = s.indexOf('#');
        int count = Integer.parseInt(s.substring(0, j));
        if (count == 0) return new ArrayList<>();

        String encoded = s.substring(j + 1);
        List<String> result = new ArrayList<>();
        StringBuilder current = new StringBuilder();

        int i = 0;
        while (i < encoded.length()) {
            if (encoded.charAt(i) == ':' && i + 1 < encoded.length()) {
                if (encoded.charAt(i + 1) == ':') {
                    current.append(':');
                    i += 2;
                } else if (encoded.charAt(i + 1) == '/') {
                    current.append('/');
                    i += 2;
                } else {
                    current.append(encoded.charAt(i));
                    i++;
                }
            } else if (encoded.charAt(i) == '/') {
                result.add(current.toString());
                current.setLength(0);
                i++;
            } else {
                current.append(encoded.charAt(i));
                i++;
            }
        }
        result.add(current.toString());
        return result;
    }
}
Python 3.12
from typing import List


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

    def decode(self, s: str) -> List[str]:
        j = s.index("#")
        count = int(s[:j])
        if count == 0:
            return []

        encoded = s[j + 1:]
        result = []
        current = []
        i = 0

        while i < len(encoded):
            if encoded[i] == ":" and i + 1 < len(encoded):
                if encoded[i + 1] == ":":
                    current.append(":")
                    i += 2
                elif encoded[i + 1] == "/":
                    current.append("/")
                    i += 2
                else:
                    current.append(encoded[i])
                    i += 1
            elif encoded[i] == "/":
                result.append("".join(current))
                current = []
                i += 1
            else:
                current.append(encoded[i])
                i += 1

        result.append("".join(current))
        return result
Go 1.26
import (
    "strconv"
    "strings"
)

func encode(strs []string) string {
    var sb strings.Builder
    sb.WriteString(strconv.Itoa(len(strs)))
    sb.WriteByte('#')
    for k, s := range strs {
        if k > 0 {
            sb.WriteByte('/')
        }
        for _, c := range s {
            if c == ':' {
                sb.WriteString("::")
            } else if c == '/' {
                sb.WriteString(":/")
            } else {
                sb.WriteRune(c)
            }
        }
    }
    return sb.String()
}

func decode(s string) []string {
    j := strings.Index(s, "#")
    count, _ := strconv.Atoi(s[:j])
    if count == 0 {
        return []string{}
    }

    encoded := s[j+1:]
    result := []string{}
    var current strings.Builder

    i := 0
    for i < len(encoded) {
        if encoded[i] == ':' && i+1 < len(encoded) {
            if encoded[i+1] == ':' {
                current.WriteByte(':')
                i += 2
            } else if encoded[i+1] == '/' {
                current.WriteByte('/')
                i += 2
            } else {
                current.WriteByte(encoded[i])
                i++
            }
        } else if encoded[i] == '/' {
            result = append(result, current.String())
            current.Reset()
            i++
        } else {
            current.WriteByte(encoded[i])
            i++
        }
    }
    result = append(result, current.String())
    return result
}

Frequently asked questions

What is the optimal time complexity of Encode and Decode Strings?

The most efficient approach in this guide ("Escaping Delimiter") runs in O(n) where n is the total number of characters across all strings time and uses O(n) for the encoded/decoded output extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Encode and Decode Strings use?

Encode and Decode Strings is a medium-level Arrays & Hashing problem involving String, Design. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Encode and Decode Strings be solved without extra space?

The most space-efficient approach in this guide uses O(n) for the encoded/decoded output extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n) for the encoded/decoded output, while the optimized version uses O(n) for the encoded/decoded output.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Loading editor...
Input
strs=
["ratta","algorithm","debug","compile"]
Expected Output
["ratta","algorithm","debug","compile"]