Knowledge Guide
Home › DSA › Advanced Patterns

medium Encode and Decode Strings

Problem Statement

Design an algorithm to implement these two functions: one that can effectively convert the list of strings to a single string (encoding) and another that can revert this single string back to the original list (decoding).

Constraints:

Machine 1 (Sender):

Machine 2 (Receiver):

Ensure that after sending the encoded string from Machine 1 to Machine 2, the list of strings obtained on Machine 2 is exactly the same as the one sent from Machine 1.

Examples

  1. Example 1:

    • Input: strs = ["dog", "cat", "bird"]
    • Expected Output: ["dog", "cat", "bird"]
    • Justification: The list of strings contains three simple words. The encoded version should accurately store each word, and the decode function should reconstruct the exact original list.

  2. Example 2:

    • Input: strs = ["hello,world", "foo!bar", ""]
    • Expected Output: ["hello,world", "foo!bar", ""]
    • Justification: This test case includes strings with special characters like commas and exclamation marks, as well as an empty string. The encoding must handle special characters and empty strings properly without losing any data.

  3. Example 3:

    • Input: strs = ["", "", "empty"]
    • Expected Output: ["", "", "empty"]
    • Justification: This test case includes multiple empty strings and a non-empty string. The encoding should differentiate between multiple empty strings and preserve the original order and count of the strings.

Constraints:

Try it yourself

Try solving this question here:

✅ Solution Encode and Decode Strings

Problem Statement

Design an algorithm to implement these two functions: one that can effectively convert the list of strings to a single string (encoding) and another that can revert this single string back to the original list (decoding).

Constraints:

  • You cannot use any serialization methods such as eval.
  • The goal is to ensure that after encoding and then decoding, the output is identical to the input.

Machine 1 (Sender):

  • encode(List<String> strs): Takes a list of strings and converts it to a single encoded string.

Machine 2 (Receiver):

  • decode(String s): Takes the encoded string and reconstructs the original list of strings.

Ensure that after sending the encoded string from Machine 1 to Machine 2, the list of strings obtained on Machine 2 is exactly the same as the one sent from Machine 1.

Examples

  1. Example 1:

    • Input: strs = ["dog", "cat", "bird"]
    • Expected Output: ["dog", "cat", "bird"]
    • Justification: The list of strings contains three simple words. The encoded version should accurately store each word, and the decode function should reconstruct the exact original list.

  2. Example 2:

    • Input: strs = ["hello,world", "foo!bar", ""]
    • Expected Output: ["hello,world", "foo!bar", ""]
    • Justification: This test case includes strings with special characters like commas and exclamation marks, as well as an empty string. The encoding must handle special characters and empty strings properly without losing any data.

  3. Example 3:

    • Input: strs = ["", "", "empty"]
    • Expected Output: ["", "", "empty"]
    • Justification: This test case includes multiple empty strings and a non-empty string. The encoding should differentiate between multiple empty strings and preserve the original order and count of the strings.

Constraints:

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

Solution

To solve this problem, we encode a list of strings into a single string by storing each string's length followed by a special separator (#) and then the string itself. This approach helps us keep track of each string's length, making it easy to decode them later. The length acts as a marker that tells us where each string starts and ends, allowing the decode function to reconstruct the original list of strings accurately.

During decoding, we read the encoded string from the beginning, finding the separator (#) to determine the length of each encoded string segment. With the length information, we can extract each string correctly and add it back to the list. This method is efficient because it avoids complex parsing and uses a simple marker-based strategy to keep the encoded format clear and easy to decode.

Step-by-Step Algorithm

Encoding:

  1. Initialize encoded_string: Create an empty StringBuilder named encoded_string to store the final encoded string.
  2. Iterate through the input list strs: Loop through each string s in the list strs.
    • Calculate and Append Length: For each string s, calculate its length using s.length().
    • Append Separator and String: Append the length, followed by the separator #, and then the string s itself to encoded_string.
    • Purpose: The length and separator # help to differentiate between strings during decoding.
  3. Return Encoded String: Convert the StringBuilder to a string using toString() and return it. This string represents the entire list in an encoded format.

Decoding:

  1. Initialize List strs: Create an empty list strs to store the decoded strings.
  2. Initialize Pointer i: Start with i = 0, pointing to the beginning of the encoded string s.
  3. Iterate through Encoded String s: Use a while loop to process the entire encoded string until i reaches the end.
    • Find the Next Separator #: Locate the next # separator using s.indexOf('#', i).
    • Extract Length: Extract the substring from i to the position of # to get the length of the next string. Convert this length from a string to an integer using Integer.parseInt.
    • Extract String: Use the extracted length to get the actual string segment from the encoded string, starting just after # for length characters.
    • Add to List: Append the extracted string to the list strs.
    • Update Pointer i: Move the pointer i to the position after the extracted string to continue processing.
  4. Return Decoded List: After processing all strings, return the list strs.

Algorithm Walkthrough

Input: ["hello,world", "foo!bar", ""]

Image
Image
  1. Encoding:
    • Input List: ["hello,world", "foo!bar", ""]
    • Initialize encoded_string as an empty StringBuilder.
    • For the first string "hello,world":
      • Length is 11. Append 11#hello,world to encoded_string.
    • For the second string "foo!bar":
      • Length is 7. Append 7#foo!bar to encoded_string.
    • For the third string "":
      • Length is 0. Append 0# to encoded_string.
    • Encoded Result: encoded_string becomes "11#hello,world7#foo!bar0#".
Image
Image
  1. Decoding:
    • Encoded String: "11#hello,world7#foo!bar0#"
    • Initialize strs as an empty list and set i = 0.
    • First Decoding Step:
      • Find # at position 2. Extract length 11 from s.substring(0, 2).
      • Extract "hello,world" using s.substring(3, 14).
      • Add "hello,world" to strs.
      • Update i to 14 (end of the extracted string).
    • Second Decoding Step:
      • Find # at position 15. Extract length 7 from s.substring(14, 15).
      • Extract "foo!bar" using s.substring(16, 23).
      • Add "foo!bar" to strs.
      • Update i to 23.
    • Third Decoding Step:
      • Find # at position 24. Extract length 0 from s.substring(23, 24).
      • Extract an empty string "".
      • Add "" to strs.
      • Update i to 25.
    • Final Decoded List: ["hello,world", "foo!bar", ""].

Code

java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {

  // Function to encode a list of strings
  public String encode(List<String> strs) {
    // StringBuilder to build the encoded string
    StringBuilder encoded_string = new StringBuilder();

    // Iterate through each string in the list
    for (String s : strs) {
      // Append the length of the string followed by a '#' separator
      encoded_string.append(s.length()).append("#").append(s);
      // The length helps in decoding the exact number of characters for each string
    }
    // Return the final encoded string containing all strings in the desired format
    return encoded_string.toString();
  }

  // Function to decode the single string back to a list of strings
  public List<String> decode(String s) {
    List<String> strs = new ArrayList<>();
    int i = 0;

    // Process the encoded string until all characters are decoded
    while (i < s.length()) {
      // Find the position of the next '#' separator
      int j = s.indexOf('#', i);
      // Extract the length of the next string using the substring before '#'
      int length = Integer.parseInt(s.substring(i, j));
      // Extract the actual string using the calculated length
      strs.add(s.substring(j + 1, j + 1 + length));
      // Move the pointer to the next encoded string part
      i = j + 1 + length;
    }
    // Return the decoded list of strings
    return strs;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    List<String> strs1 = Arrays.asList("dog", "cat", "bird");
    List<String> strs2 = Arrays.asList("hello,world", "foo!bar", "");
    List<String> strs3 = Arrays.asList("", "", "empty");

    // Encode and then decode the strings to test the correctness
    String encoded1 = sol.encode(strs1);
    String encoded2 = sol.encode(strs2);
    String encoded3 = sol.encode(strs3);

    // Output the results to verify that the decoded strings match the original input
    System.out.println(sol.decode(encoded1)); // Output: ["dog", "cat", "bird"]
    System.out.println(sol.decode(encoded2)); // Output: ["hello,world", "foo!bar", ""]
    System.out.println(sol.decode(encoded3)); // Output: ["", "", "empty"]
  }
}

Complexity Analysis

Time Complexity

Encode Function:

  • The encode function goes through each string in the list once. For each string, it calculates the length and appends it with a separator (#) to the result.
  • The total time taken depends on the total number of characters across all strings, which is N.

Time Complexity of encode: , where N is the total number of characters in all strings.

Decode Function:

  • The decode function scans through the entire encoded string once. It finds each separator (#) and extracts the original strings based on their lengths.
  • The time taken is also proportional to the total length of the encoded string, which is N.

Time Complexity of decode: , where N is the total length of the encoded string.

Space Complexity

  1. Encoding:

    • The space complexity of the encode method is , where N is the length of the final encoded string stored in the StringBuilder.

  2. Decoding:

    • The space complexity of the decode method is for storing the result list, where M is the number of strings obtained after the split operation. Since M can be proportional to N (the size of the input string), the overall space complexity is .
🤖 Don't fully get this? Learn it with Claude

Stuck on Encode and Decode Strings? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Encode and Decode Strings** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Encode and Decode Strings** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Encode and Decode Strings**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Encode and Decode Strings**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Range Frequency QueriesSerialize and Deserialize BST →