Encode and Decode Strings medium

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.

Please note: The encoded string on the network is limited to 4096 characters. Therefore, you should consider using a separator between the strings.

Example 1

Input: ["Hello", "World"] Output: ["Hello", "World"] Explanation: The function should return the original array.

Example 2

Input: ["We", "are", "in", "the", "middle", "of", "winter"] Output: ["We", "are", "in", "the", "middle", "of", "winter"] Explanation: The function should return the original array.

Steps

1. Encoding:

   • Choose a separator character that is unlikely to appear within the strings themselves (e.g., a character with a high ASCII value or a special character like #).
   • Concatenate the strings with the separator character in between. Prepend the length of each string to the string itself, separated by a different character (e.g., :). This allows us to reconstruct the strings during decoding even if the separator appears within a string.

2. Decoding:

   • Split the encoded string using the separator.
   • For each substring:
     • Extract the length of the string.
     • Extract the string itself (using substring).
     • Add the extracted string to the result array.

Explanation

The key to solving this problem efficiently and handling potential issues (strings containing the separator) is to prepend the length of each string. This allows the decoder to know exactly how many characters to read for each string, regardless of whether the separator character appears within the string's content.

Code

function encode(strs: string[]): string {
    let encodedString = "";
    for (const str of strs) {
        encodedString += str.length + ":" + str + "#"; 
    }
    return encodedString;
};


function decode(s: string): string[] {
    const result: string[] = [];
    let i = 0;
    while (i < s.length) {
        const colonIndex = s.indexOf(':', i);
        const length = parseInt(s.substring(i, colonIndex));
        const hashIndex = s.indexOf('#', colonIndex + 1);
        const str = s.substring(colonIndex + 1, hashIndex);
        result.push(str);
        i = hashIndex + 1;
    }
    return result;
};


// Example usage
const strs = ["We", "are", "in", "the", "middle", "of", "winter"];
const encoded = encode(strs);
const decoded = decode(encoded);
console.log("Original:", strs);
console.log("Encoded:", encoded);
console.log("Decoded:", decoded);

Complexity

Encoding:

• Time Complexity: O(N*M), where N is the number of strings and M is the average length of the strings. We iterate through each string and append to the encoded string.
• Space Complexity: O(N*M), The space used to store the encoded string is proportional to the total length of all input strings.

Decoding:

• Time Complexity: O(N*M) for the same reasons as encoding. We iterate through the encoded string.
• Space Complexity: O(N*M), The space used to store the decoded array is proportional to the total length of all strings.