Skip to content
AI360Xpert
Back to Arrays & Hashing
Medium

Encode and Decode Strings

Design an algorithm to encode a list of strings to a single string. The encoded string is then sent over the network and is decoded back to the original list of strings. Please implement `encode` and `decode` methods.

Examples

Input:strs = ["lint","code","love","you"]
Output:["lint","code","love","you"]
One possible encode method is: "lint:;code:;love:;you"
Input:strs = ["we", "say", ":", "yes"]
Output:["we", "say", ":", "yes"]
The delimiter used must handle edge cases where the strings themselves contain the delimiter.

Constraints

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

Length + Delimiter (Optimal)

Approach

To correctly decode the strings, we need a way to distinguish where one string ends and another begins. A simple delimiter like a comma or colon is insufficient because the strings themselves can contain these characters. Instead, we can prefix each string with its length followed by a special delimiter (e.g., `#`). For example, the string "lint" becomes "4#lint". During decoding, we read the length until we hit the `#`, then read that exact number of characters to extract the string.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(n)

Where n is the total number of characters across all strings. This approach handles all edge cases perfectly since we know exactly how many characters to read for each string.

Solution.java
class Solution {    // Encodes 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();    }
    // Decodes a single string to a list of strings.    public List<String> decode(String s) {        List<String> res = new ArrayList<>();        int i = 0;        while (i < s.length()) {            int j = i;            // Find the delimiter '#'            while (s.charAt(j) != '#') {                j++;            }            // Extract the length of the next string            int length = Integer.parseInt(s.substring(i, j));            // Extract the string and add to result            res.add(s.substring(j + 1, j + 1 + length));            // Move pointer to the start of the next string segment            i = j + 1 + length;        }        return res;    }}