Encode and Decode Strings - Solution & Explanation

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.

MediumPremiumFree on FleetCodeArray String Design7 min readAsked at: Amazon, Microsoft, Meta +8

Practice this problem

Problem Statement

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).

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Detailed 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

Video Solution

Encode and Decode Strings - Leetcode 271 - Python • NeetCode • 495,123 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Encode and Decode Strings with our built-in code editor and test cases.

Practice on FleetCode

Count and Say

Count Binary Substrings

Problem Info

DifficultyMedium

Acceptance51.9%

Approaches1

Reading time7 min

Asked at

Amazon Microsoft Meta Oracle CrowdStrike