Start learning free

LESSON 318 OF 536 · HASH TABLE

Encode and Decode Strings in JavaScript: Length Prefixes in O(N)

Practice O(n) Read the full explanation

Design a way to turn a list of strings into one string and back. One program encodes the list and sends the string to another program, which decodes it into the same list of strings, in the same order.

Implement the class Codec:

  • encode(strs) gets a list of strings strs and returns one string that holds all of them.
  • decode(s) gets a string s made by encode and returns the original list of strings.

The strings can contain any printable character, including #, digits and spaces, and a string can be empty. So no single character can mark where one string ends and the next begins: that character could be inside a string too.

Each test is one list. It is encoded with one Codec object and decoded with another, as if the string were sent to another machine, so decode can use only the string it gets. The output is the decoded list. The starter code spells the method names the way your language does.

 

Example 1:

Input: strs = ["lint","code","love","you"]
Output: ["lint","code","love","you"]
Explanation: encode can return "4#lint4#code4#love3#you": for each string, its length,
a #, then the string itself. decode reads the 4 before the first #, takes the 4 characters
after it, "lint", and goes on from there.

Example 2:

Input: strs = ["3#a","","#"]
Output: ["3#a","","#"]
Explanation: The encoded string is "3#3#a0#1##". decode reads the length 3 up to the first #,
then takes exactly 3 characters, "3#a", although they hold a digit and a #.
Then "0#" gives the empty string, and "1##" gives "#".

Example 3:

Input: strs = []
Output: []
Explanation: An empty list encodes to the empty string "", which decodes to no strings at all.
A list with one empty string, [""], encodes to "0#" instead, so the two stay different.

 

Constraints:

  • 0 <= strs.length <= 105
  • 0 <= strs[i].length <= 200
  • The total length of all the strings is at most 106.
  • strs[i] consists of printable ASCII characters (codes 32 to 126): letters, digits, spaces and punctuation such as #.

Note:

Both encode and decode should run in O(N) time, where N is the total length of all the strings.

Write each string's length in front of it, followed by a #: <length>#<string>. To decode, read the digits up to the next #, then take exactly that many characters, whatever they are; the next string starts right after them.

Keep both methods linear: don't copy the whole encoded string again for every string you add, and don't cut s into shorter and shorter copies while decoding; move an index through it instead.

STEP 1 OF 14
    Ctrl + Enter to check

    JAVASCRIPT · HASH TABLE

    Encode And Decode Strings in JavaScript, explained

    Problem overview

    The class Codec has two methods. encode(strs) turns an array of strings into one string, and decode(s) turns that string back into the same array, in the same order. The two methods run on different Codec objects, so decode can rely only on the string it receives, not on anything encode remembered.

    The strings may hold any printable character, including digits, spaces and #, and they may be empty. For ["lint", "code", "love", "you"] the encoded string is "4#lint4#code4#love3#you", and decoding it gives the same four strings. For ["3#a", "", "#"] it is "3#3#a0#1##". The empty array encodes to the empty string, and [""] encodes to "0#", so the two can't be confused.

    Approach: write the length first

    The obvious idea is to join the strings with a separator such as #. It fails because any character you pick can also appear inside a string: ["a#b"] and ["a", "b"] would both become "a#b".

    A length prefix avoids the problem. Before each string, write how many characters it has, then a #, then the string. When decoding, you read the digits up to the next #, turn them into a number, and take exactly that many characters. Those characters are never inspected, so a # or a digit inside them can't be mistaken for a marker. The # after the length is still needed: without it, "3abc" followed by "12" would be ambiguous about where the length ends and the text begins.

    Both methods can run in O(N), where N is the total length of all strings. Two things would break that: copying the whole encoded string again for every piece, and cutting s into shorter and shorter copies while decoding. The solution builds the result once and moves an index through s instead.

    Step by step

    encode

    1. Start encoded as an empty string, declared with let because it grows.
    2. Loop over the strings with for...of, taking each one as s.
    3. Append the length, a # and the string itself. Adding a number to a string turns the number into its digits, so s.length + "#" + s works without a conversion call.
    4. Return encoded after the loop.

    decode

    1. Create the result array strs and an index i that marks where the next piece starts.
    2. Loop while i < s.length. An empty s never enters the loop, which gives the empty array.
    3. Start j at i and move it forward until s[j] is "#". Because a length contains only digits, the first # found from i is the one encode wrote after it.
    4. Read the digits with s.substring(i, j) and convert them with Number.
    5. Push the next length characters, which start at j + 1, onto strs.
    6. Set i to j + 1 + length, the start of the next piece.
    7. Return strs.

    The solution in JavaScript

    class Codec {
    encode(strs) {
        let encoded = "";
        for (const s of strs) {
            encoded += s.length + "#" + s;
        }
        return encoded;
    }

    decode(s) {
        const strs = [];
        let i = 0;
        while (i < s.length) {
            let j = i;
            while (s[j] !== "#") {
                j++;
            }
            const length = Number(s.substring(i, j));
            strs.push(s.substring(j + 1, j + 1 + length));
            i = j + 1 + length;
        }
        return strs;
    }
}

    The JavaScript details worth knowing:

    • + with a string. In s.length + "#" + s, the first + has a number on the left and a string on the right, so JavaScript converts the number to text and joins them. Starting encoded as "" keeps every += a string operation.
    • substring(start, end) stops before end. It takes the characters from start up to but not including end, so substring(j + 1, j + 1 + length) returns exactly length characters. If end goes past the string, it is clamped to the string's length rather than raising an error.
    • Number("12") is 12. Unlike parseInt, Number turns the whole text into a number or gives NaN. Here the text is always digits made by encode.
    • !== compares without converting. s[j] !== "#" compares two strings directly.

    Complexity

    Time: O(N). encode appends one piece per string, and each character is written once, plus a few characters for each length and #. decode moves j over each length's digits and copies each string once, and i only moves forward. The digits of the lengths add at most a few characters per string, and the constraints keep each string under 200 characters, so a length has at most three digits.

    Space: O(N) for the encoded string and for the decoded array, apart from a few variables.

    Edge cases and common mistakes

    • Empty list and list with an empty string. [] gives "" and [""] gives "0#". Decoding "0#" pushes substring(2, 2), the empty string, and moves i to 2, which ends the loop.
    • Strings that look like an encoding. ["12#ab"] encodes to "5#12#ab". The decoder reads 5, takes five characters, and never treats the inner 12# as a length.
    • Splitting on #. Calling s.split("#") in decode breaks as soon as a string holds a #.
    • Forgetting the separator after the length. Without the #, "12" after a string of length 3 would read as 312.
    • Slicing s repeatedly. Writing s = s.substring(...) to drop each piece copies the rest of the string every time, which makes decode quadratic on long inputs.

    Testing

    • ["a", "b"] encodes to "1#a1#b" and decodes back to ["a", "b"].
    • ["", "", ""] encodes to "0#0#0#" and decodes to three empty strings.
    • ["3#a", "", "#"] encodes to "3#3#a0#1##" and decodes to the same array.
    • ["12#ab"] encodes to "5#12#ab" and decodes to ["12#ab"].
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free