Start learning free

LESSON 317 OF 535 · HASH TABLE

Encode and Decode Strings in C++: 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

    C++ · HASH TABLE

    Encode And Decode Strings in C++, explained

    Problem overview

    The class Codec has two methods. encode takes a vector<string> and returns one string that holds all of them. decode takes that string, and nothing else, and rebuilds the original vector: the same strings in the same order. A test encodes with one Codec object and decodes with another, so no information can travel except the encoded string itself.

    The strings can hold any printable character, including #, digits and spaces, and a string can be empty. The list itself can also be empty. Take ["3#a", "", "#"]: it has to come back as exactly three strings, the first one containing a digit and a hash, the second one empty, the third one a lone hash.

    Both methods must run in O(N) time, where N is the total length of all the strings.

    Approach: say how long each string is

    The obvious idea is to join the strings with a separator and split on it when decoding. It fails because the separator can appear inside a string. Joining "a#b" and "c" with # after each string gives a#b#c#, and splitting that on # produces three strings, not two. Any single character you pick can be part of the data, so a separator alone can never be reliable.

    The fix is to stop searching for where a string ends and write it down instead. In front of each string, put its length, then a #, then the string. Decoding reads the digits up to the first #, converts them to a number, and then takes exactly that many characters without looking at what they are. A # or a digit inside the string is just a character that is part of the count. The next piece starts right after those characters.

    The # after the length is still needed, because lengths have different numbers of digits. Without it, a string that starts with a digit would run into its own length, and 1 followed by "2" could not be told apart from 12. The reader only ever looks for a # while it is reading a length, and a length is made of digits only, so the first # it meets is always the one that encode wrote.

    For ["lint", "code", "love", "you"] the encoded string is 4#lint4#code4#love3#you. For ["3#a", "", "#"] it is 3#3#a0#1##. An empty list encodes to the empty string, and [""] encodes to 0#, so those two inputs stay different.

    Step by step

    For encode:

    1. Create an empty string named encoded. It collects the pieces.
    2. Loop over strs with a range-based for, taking each element as const string& s. The reference avoids copying every string just to look at it.
    3. Append the piece with +=: the length as text, a #, then the string. to_string turns the number into digits.
    4. Return encoded after the loop.

    For decode:

    1. Create the result vector strs, empty.
    2. Keep an index i starting at 0. It always marks where the next piece begins.
    3. Loop while i < s.size(). Each round reads one complete piece, so an empty s never enters the loop.
    4. Find the #. Start j at i and move it forward while s[j] is not '#'. The digits of the length are the characters from i up to, but not including, j.
    5. Convert the digits. s.substr(i, j - i) copies them, because substr takes a start position and a length, and stoi turns that text into the int named length.
    6. Take the string. It starts right after the #, at j + 1, and is exactly length characters long. Push it into strs.
    7. Move i to j + 1 + length, the start of the next piece. Moving an index forward is what keeps the work linear: cutting s shorter after every piece would copy the rest of it again and again.
    8. Return strs.

    The solution in C++

    class Codec {
public:
    string encode(vector<string>& strs) {
        string encoded;
        for (const string& s : strs) {
            encoded += to_string(s.size()) + "#" + s;
        }
        return encoded;
    }

    vector<string> decode(string s) {
        vector<string> strs;
        int i = 0;
        while (i < s.size()) {
            int j = i;
            while (s[j] != '#') {
                j++;
            }
            int length = stoi(s.substr(i, j - i));
            strs.push_back(s.substr(j + 1, length));
            i = j + 1 + length;
        }
        return strs;
    }
};

    C++ details worth a closer look:

    • to_string(s.size()). size() returns an unsigned type, and to_string has an overload for it, so the length is written as plain digits.
    • += grows in place. encoded += x appends to the existing string and reuses its spare capacity, so building the result piece by piece is linear. Writing encoded = encoded + x would build a new string each time and copy everything collected so far.
    • const string&. A reference to a constant string reads each element without copying it. Plain string s in the loop would copy every string.
    • substr(pos, count). The second argument is a length, not an end position. That is why the digits are s.substr(i, j - i), and why the payload is s.substr(j + 1, length).
    • i < s.size() with an int. Comparing a signed int with an unsigned size() compiles, and some compilers warn about it. It is safe here because i is never negative.
    • Parameters. encode takes strs by reference, because a vector passed by value is copied. decode takes s by value, which costs one copy of the whole encoded string. That copy is O(N), so the total stays linear.
    • The inner loop trusts the input. It stops only at a #, so it relies on s having been produced by encode. A string without a # would run past the end.

    Complexity

    Time: O(N). encode appends each string once, plus a few characters for its length and the #. decode moves i and j forward only, so each character of the encoded string is looked at a constant number of times, and each payload is copied once by substr. The encoded string is longer than N by the length prefixes, a few characters per string, so the work is linear in the size of the encoded string.

    Space: O(N) for the encoded string and for the decoded vector. Apart from the output, the methods use a handful of integers.

    Edge cases and common mistakes

    • An empty list. It encodes to "" and decodes to an empty vector, because the while loop never runs.
    • Empty strings. [""] encodes to 0# and ["", ""] to 0#0#. Each decodes to the right number of empty strings, since a length of 0 gives substr(j + 1, 0), which is empty.
    • A # or digits inside a string. ["a#b", "12", "c"] works for the same reason ["3#a", "", "#"] does: the decoder reads the length, then skips exactly that many characters without examining them.
    • Splitting on #. Looking for the next # in the whole string, rather than only in the digits after i, breaks as soon as a string contains a hash.
    • Leaving out the #. Without the marker, lengths and string starts blend together when a string begins with a digit.
    • Forgetting 1 + . The next piece starts at j + 1 + length. Using j + length lands one character too early, on the last character of the payload.
    • Cutting the string down. Calling s = s.substr(...) after each piece copies the remaining text every round, which makes decoding quadratic.

    Testing

    These round trips all decode back to the input:

    • ["lint", "code", "love", "you"] encodes to 4#lint4#code4#love3#you.
    • ["3#a", "", "#"] encodes to 3#3#a0#1##.
    • [] encodes to the empty string and decodes to [].
    • [""] encodes to 0#.
    • ["", ""] encodes to 0#0#.
    • ["hello world", "12", "a#b#c"] encodes to 11#hello world2#125#a#b#c. Reading it back, the length 11 takes hello world, and the 12 in the data is not mistaken for a length.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free