271. Encode and Decode Strings Solution

Q: Is Encode and Decode Strings easy or hard?

Encode and Decode Strings is generally rated medium difficulty. The implementation is straightforward once you realize the length-prefix trick, but many candidates initially struggle with designing a format that handles arbitrary characters safely.

Q: Encode and Decode Strings Python/Java solution

In Python or Java, implement encode by concatenating # for each input string. For decode, iterate through the encoded string, parse digits until '#', convert to an integer length, then extract the next substring of that size and append it to the result list.

The problem

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
  //... your code
  return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

You are not allowed to solve the problem using any serialize methods (such as eval).

Example 1:

Input: dummy_input = ["Hello","World"]
Output: ["Hello","World"]
Explanation:
Machine 1:
Codec encoder = new Codec();
String msg = encoder.encode(strs);
Machine 1 ---msg---> Machine 2

Machine 2:
Codec decoder = new Codec();
String[] strs = decoder.decode(msg);

Example 2:

Input: dummy_input = [""]
Output: [""]

Constraints:

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

Follow up: Could you write a generalized algorithm to work on any possible set of characters?

Approach overview

Problem Overview: You need to design two functions: encode converts a list of strings into a single string, and decode reconstructs the original list from that encoded string. The tricky part is preserving boundaries between strings without losing information, even when the strings contain special characters.

Approach 1: Delimiter-Based Encoding (O(n) time, O(n) space)

A straightforward idea is to join all strings using a delimiter such as # or |. During decoding, split the encoded string by that delimiter. The problem appears when original strings themselves contain the delimiter. You would need an escaping mechanism (for example replacing # with ##) before encoding and reversing the process during decoding. This works but adds extra processing logic and edge cases.

Approach 2: Length-Prefix Encoding (O(n) time, O(n) space)

The robust solution stores the length of each string before the string itself. For every word s, append len(s), a separator (commonly #), and the string. Example: ["leet","code"] becomes 4#leet4#code. During decoding, iterate through the encoded string, read characters until the separator to determine the length, convert it to an integer, then extract the next length characters as the original string. Repeat until the string ends.

This approach works regardless of the content of the strings because the boundary is defined by length rather than a special character. The decoding process simply scans the string, parses the numeric prefix, and slices the substring accordingly. Every character is processed once, giving linear complexity.

The technique is essentially a small protocol design problem, which is why the problem is tagged under design. The implementation mainly uses sequential traversal of a string and storage in a dynamic list or array.

Recommended for interviews: Length-prefix encoding is the expected answer. It avoids delimiter conflicts and guarantees correct decoding in O(n) time. Mentioning the delimiter idea first shows you considered simpler designs, but implementing the length-prefix protocol demonstrates stronger problem-solving and system design thinking.

Solution

During encoding, we convert the length of the string into a fixed 4-digit string, add the string itself, and append it to the result string in sequence.

During decoding, we first take the first four digits of the string to get the length, and then cut the following string according to the length. We cut it in sequence until we get the list of strings.

The time complexity is O(n).

Python

class Codec:
    def encode(self, strs: List[str]) -> str:
        """Encodes a list of strings to a single string."""
        ans = []
        for s in strs:
            ans.append('{:4}'.format(len(s)) + s)
        return ''.join(ans)

    def decode(self, s: str) -> List[str]:
        """Decodes a single string to a list of strings."""
        ans = []
        i, n = 0, len(s)
        while i < n:
            size = int(s[i : i + 4])
            i += 4
            ans.append(s[i : i + size])
            i += size
        return ans


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))

Java

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder ans = new StringBuilder();
        for (String s : strs) {
            ans.append((char) s.length()).append(s);
        }
        return ans.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> ans = new ArrayList<>();
        int i = 0, n = s.length();
        while (i < n) {
            int size = s.charAt(i++);
            ans.add(s.substring(i, i + size));
            i += size;
        }
        return ans;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));

C++

class Codec {
public:
    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string ans;
        for (string s : strs) {
            int size = s.size();
            ans += string((const char*) &size, sizeof(size));
            ans += s;
        }
        return ans;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        vector<string> ans;
        int i = 0, n = s.size();
        int size = 0;
        while (i < n) {
            memcpy(&size, s.data() + i, sizeof(size));
            i += sizeof(size);
            ans.push_back(s.substr(i, size));
            i += size;
        }
        return ans;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(strs));

type Codec struct {
}

// Encodes a list of strings to a single string.
func (codec *Codec) Encode(strs []string) string {
	ans := &bytes.Buffer{}
	for _, s := range strs {
		t := fmt.Sprintf("%04d", len(s))
		ans.WriteString(t)
		ans.WriteString(s)
	}
	return ans.String()
}

// Decodes a single string to a list of strings.
func (codec *Codec) Decode(strs string) []string {
	ans := []string{}
	i, n := 0, len(strs)
	for i < n {
		t := strs[i : i+4]
		i += 4
		size, _ := strconv.Atoi(t)
		ans = append(ans, strs[i:i+size])
		i += size
	}
	return ans
}

// Your Codec object will be instantiated and called as such:
// var codec Codec
// codec.Decode(codec.Encode(strs));

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Delimiter-Based Encoding	O(n)	O(n)	Quick prototype when input is guaranteed not to contain the delimiter or when escaping is acceptable
Length-Prefix Encoding	O(n)	O(n)	General case solution that works for any characters in the input strings

Frequently asked questions

Is Encode and Decode Strings easy or hard?

Encode and Decode Strings is generally rated medium difficulty. The implementation is straightforward once you realize the length-prefix trick, but many candidates initially struggle with designing a format that handles arbitrary characters safely.

Encode and Decode Strings Python/Java solution

In Python or Java, implement encode by concatenating <length>#<string> for each input string. For decode, iterate through the encoded string, parse digits until '#', convert to an integer length, then extract the next substring of that size and append it to the result list.

How to solve Encode and Decode Strings in O(n)?

Use a length-prefix format. During encoding, append the length of each string followed by a separator like '#', then the string itself. During decoding, iterate through the encoded string, parse the number before '#', and extract that many characters as the original string. Each character is scanned once, giving O(n) complexity.

What is the best approach for Encode and Decode Strings?

Length-prefix encoding is the most reliable approach. Each string is stored as <length>#<string>, allowing the decoder to read the exact number of characters for each element. This avoids delimiter conflicts and runs in O(n) time with O(n) space.

Is Encode and Decode Strings asked at Google/Amazon/Meta?

Encode and Decode Strings is a common design-style interview problem and has appeared in interviews at companies like Google, Meta, and Amazon. It tests your ability to design a simple serialization format and handle edge cases with string parsing.

What data structure is used in Encode and Decode Strings?

The solution mainly uses strings for encoding and an array or list to store the decoded results. The algorithm relies on sequential string traversal and substring extraction rather than complex data structures.

What is the time complexity of Encode and Decode Strings?

Both encoding and decoding run in O(n) time where n is the total number of characters across all strings. Each character is processed once while building the encoded string and once while parsing it during decoding. Space complexity is also O(n) because the encoded representation stores all characters.

Encode and Decode Strings solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Encode and Decode Strings solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems