Start learning free

LESSON 321 OF 539 · 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 List<string> and returns one string that holds all of them. Decode takes that string, built by a different Codec object, and returns the original list in the same order. Decode can use only the string it receives, with no shared state.

    The strings are printable ASCII and may contain #, digits and spaces. A string can also be empty, and the list can be empty.

    For ["lint", "code", "love", "you"], one valid encoding is 4#lint4#code4#love3#you. For ["3#a", "", "#"] the encoding is 3#3#a0#1##, and decoding it returns exactly the same three strings. An empty list encodes to the empty string, while [""] encodes to 0#, so the two are never confused.

    Approach: write the length first

    The obvious plan is to join the strings with a separator, such as a comma or a #, and split on it later. That fails here because any printable character can appear inside a string, so the separator may also be part of the data. Escaping the separator works but makes the code fiddly.

    A cleaner idea is to say how long each string is before writing it. Each string becomes <length>#<string>. When decoding, read the digits up to the next #, convert them to a number, and take exactly that many characters. Those characters are never inspected, so a # or a digit inside them can't confuse the decoder. The next piece starts right after them.

    The # after the length is still needed. Without it, "12" followed by a string starting with 3 would be written as 123..., and the decoder couldn't tell where the length ends. The decoder only looks for a # while it is reading a length, and a length consists of digits only, so the first # it meets is the right one.

    Both methods must run in O(N), where N is the total length of all the strings. That has two consequences. Encode shouldn't add to a string in a loop, because each addition copies everything built so far. Decode shouldn't cut the remaining input into shorter and shorter copies. It moves an index through the one string instead.

    Step by step

    Encode

    1. Create a StringBuilder named encoded. It collects text piece by piece without copying what is already there.
    2. Loop with foreach over the strings in strs.
    3. Append three things for each string s: its length s.Length, the character '#', and s itself. Append returns the builder, so the three calls can be chained on one line.
    4. Return encoded.ToString() after the loop.

    Decode

    1. Create the result list, strs, empty for now.
    2. Declare i as 0. It is the position where the next piece starts.
    3. Loop while i < s.Length. Each round reads one whole piece. An empty input skips the loop and returns an empty list.
    4. Start j at i to look for the # after the length's digits.
    5. Move j forward with an inner loop that runs while s[j] isn't '#'.
    6. Parse the length. The digits sit between i and j. C#'s Substring takes a start and a length, so the call is s.Substring(i, j - i), and int.Parse turns it into an int.
    7. Add the string to strs: s.Substring(j + 1, length), the length characters right after the #.
    8. Move i to j + 1 + length, the start of the next piece.
    9. Return strs after the loop.

    The solution in C#

    class Codec {
    public string Encode(List<string> strs) {
        StringBuilder encoded = new StringBuilder();
        foreach (string s in strs) {
            encoded.Append(s.Length).Append('#').Append(s);
        }
        return encoded.ToString();
    }

    public List<string> Decode(string s) {
        List<string> strs = new List<string>();
        int i = 0;
        while (i < s.Length) {
            int j = i;
            while (s[j] != '#') {
                j++;
            }
            int length = int.Parse(s.Substring(i, j - i));
            strs.Add(s.Substring(j + 1, length));
            i = j + 1 + length;
        }
        return strs;
    }
}

    The C# details worth knowing:

    • Method names are PascalCase. C# methods are conventionally Encode and Decode, not encode and decode. Names are case-sensitive, so a lowercase encode is a different, undefined method.
    • Append(int) writes the digits. StringBuilder.Append has overloads for int and char, so Append(s.Length) adds the decimal text of the number, and Append('#') adds one character. Using '#' rather than "#" avoids creating a string for one character.
    • Substring(start, length). The second argument is a count, not an end position. This differs from slice in other languages and is the usual source of off-by-one errors here.
    • Strings are immutable. Every += on a string builds a new one, so appending in a loop costs more than linear time in total. StringBuilder keeps the work linear.
    • The helper types come from namespaces. StringBuilder lives in System.Text and List<T> in System.Collections.Generic. In a file of your own, add the matching using lines.

    Complexity

    Time: O(N). Encode appends each string once, and each append costs time proportional to the characters written. Decode moves j over each length's digits and copies each string once with Substring. The index i only moves forward, so no character is scanned more than a constant number of times. The digits of the lengths add at most a few characters per string.

    Space: O(N) for the output of each method. Apart from the output, there is no extra storage beyond a few variables.

    Edge cases and common mistakes

    • Empty list. Encode returns "" and Decode("") returns an empty list.
    • List with one empty string. It encodes to 0# and decodes to [""]. This is why the length is written even when it is 0.
    • Strings that look like the format. "3#a" is read back correctly because the decoder takes exactly 3 characters after the first # and never looks inside them.
    • Using a bare separator. Joining with # breaks as soon as a string contains a #.
    • Searching for the # from the wrong place. The search must begin at i, the start of the current length. Searching from the start of s would find an earlier #.
    • Passing the wrong second argument to Substring. s.Substring(i, j) is wrong unless i is 0; the length of the digits is j - i.
    • Cutting the input down. Replacing s with s.Substring(j + 1 + length) every round copies the rest of the text each time, which makes Decode quadratic.

    Testing

    Each input below was encoded and the result decoded again:

    • ["lint", "code", "love", "you"] encodes to 4#lint4#code4#love3#you and decodes to the same list.
    • ["3#a", "", "#"] encodes to 3#3#a0#1## and decodes to the same list.
    • [] encodes to the empty string and decodes to [].
    • [""] encodes to 0# and decodes to [""].
    • ["a", "b"] encodes to 1#a1#b and decodes to ["a", "b"].
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free