6. Encode and Decode Strings

Encode and Decode Strings – Brute Force to Optimal Solutions

In this problem, we need to design an encoding and decoding mechanism for a list of strings.
The solution must handle corner cases like strings with special characters, empty strings, and delimiter issues.

Problem Statement:

You are given a list of strings. Implement two functions:

1. encode(List<String> strs): Encodes a list of strings to a single string.
2. decode(String s): Decodes the encoded string back to the original list of strings.

---

Approach 1: Brute Force (Concatenation Approach)

This simple brute-force solution tries to concatenate the strings with a delimiter like "#" and splits them later during decoding.

Code (Java):

import java.util.*;

public class Codec {
    // Encode the list of strings by concatenating them with a delimiter.
    public String encode(List<String> strs) {
        StringBuilder encodedString = new StringBuilder();
        for (String str : strs) {
            encodedString.append(str).append("#");  // Use '#' as delimiter
        }
        return encodedString.toString();
    }

    // Decode the string by splitting it using the delimiter.
    public List<String> decode(String s) {
        return Arrays.asList(s.split("#"));  // Split on '#'
    }
}

Time Complexity:

• Encode: O(n), where n is the total length of all strings.
• Decode: O(n), as splitting takes linear time.

Space Complexity: O(n) for both encoding and decoding.

---

Problem with Brute Force Solution:

The delimiter-based approach will fail if any string in the input contains the chosen delimiter (like "#"). This makes it non-reliable for general cases.

---

Approach 2: Length-Based Encoding (Optimal Solution)

To avoid issues with special characters and delimiters, we can encode each string with its length followed by the string itself. This ensures we know exactly where each string starts and ends during decoding.

Code (Java):

import java.util.*;

public class Codec {

    // Encode a list of strings with length-based encoding
    public String encode(List<String> strs) {
        StringBuilder encodedString = new StringBuilder();
        for (String str : strs) {
            encodedString.append(str.length()).append("/").append(str);  // Encode length + '/' + string
        }
        return encodedString.toString();
    }

    // Decode the string by reading each length prefix and extracting the corresponding string
    public List<String> decode(String s) {
        List<String> decodedStrings = new ArrayList<>();
        int i = 0;

        while (i < s.length()) {
            int slashIndex = s.indexOf("/", i);  // Find the separator '/'
            int length = Integer.parseInt(s.substring(i, slashIndex));  // Get the length prefix
            i = slashIndex + 1;  // Move the pointer past the '/'
            decodedStrings.add(s.substring(i, i + length));  // Extract the string of the given length
            i += length;  // Move the pointer past the extracted string
        }

        return decodedStrings;
    }
}

Time Complexity:

• Encode: O(n), where n is the total length of all strings.
• Decode: O(n), as we iterate over the entire string during decoding.

Space Complexity: O(n) for both encoding and decoding.

---

Comparison of Solutions:

Approach	Time Complexity	Space Complexity	Description	Drawbacks
Brute Force (Delimiter)	O(n)	O(n)	Simple, concatenates with "#"	Fails if input contains "#"
Length-Based Encoding	O(n)	O(n)	Uses length prefix to encode strings	Handles all edge cases properly

---

Conclusion:

The length-based encoding approach is the most optimal and reliable solution. It avoids delimiter conflicts, handles special characters, and can encode/decode efficiently. This is the recommended solution for coding interviews.