Start learning free

LESSON 301 OF 348 · STACK

Decode String in TypeScript: Stack of Counts and Buffers

Practice O(n) Read the full explanation

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.


Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Constraints:

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and square brackets '[]'.
  • s is guaranteed to be a valid input.
  • All the integers in s are in the range [1, 300].

STEP 1 OF 16
    Ctrl + Enter to check

    TYPESCRIPT · STACK

    Decode String in TypeScript, explained

    Problem overview

    The method decodeString receives an encoded string and returns the decoded one. The encoding rule is k[encoded_string]: the text inside the square brackets is repeated exactly k times. The input is always valid, k is a positive integer up to 300, and digits appear only as repeat counts, so inputs like 3a or 2[4] never occur.

    In the first example, "3[a]2[bc]" becomes "aaa" followed by "bcbc", which is "aaabcbc". In the second, "3[a2[c]]" has a group nested inside another: the inner 2[c] gives cc, so the outer group repeats acc three times and the answer is "accaccacc". In the third, "2[abc]3[cd]ef" becomes "abcabccdcdcdef", and the trailing ef is plain text outside any group.

    Approach: one entry per open bracket, plus counts

    Brackets nest, so the group that opens last is the group that closes first. That is the signature of a stack. You read the string left to right, and when a ] arrives you know exactly which text to repeat and how many times.

    This solution keeps a single stack of strings that mixes two kinds of entries:

    • a count entry, such as "3", built from the digits before a [;
    • a text entry, the decoded text collected so far for one bracket level.

    Every [ pushes a new, empty text entry. Letters are appended to the top text entry. When ] arrives, the top is the finished text and the entry just below it is its count. Pop both, repeat the text, and fold the result into whatever is now on top, because a group can itself sit inside another group.

    Here is "3[a2[c]]" as the stack evolves:

    3  ["3"]
[  ["3", ""]
a  ["3", "a"]
2  ["3", "a", "2"]
[  ["3", "a", "2", ""]
c  ["3", "a", "2", "c"]
]  ["3", "acc"]
]  ["accaccacc"]

    The brute-force alternative is to find the innermost group, expand it in place and repeat until no brackets remain. It works, but it rescans the string many times. The stack handles every character once.

    Step by step

    1. Create an empty stack of strings. It will hold counts and text buffers side by side.
    2. Loop over the characters with for...of.
    3. On [, push an empty string. This starts the text for the new group.
    4. On a letter (tested with a regular expression), make sure the stack has somewhere to put it. If the stack is empty, as it is for a leading ef, push an empty string first. Then append the letter to the last entry.
    5. On a digit, look at the top of the stack, or at an empty string if the stack is empty. If the top is not made only of digits, a new count is starting, so push the digit as its own entry. If the top is already digits, extend that number. This is how 23 stays a single count instead of becoming 2 and 3.
    6. On anything else, which can only be ], finish the group. Pop the text, then pop the count and convert it to a number.
    7. Repeat the text that many times with repeat.
    8. Fold the result back. If the stack is now empty, push the result as the first buffer. Otherwise append it to the top entry, which is the enclosing group's text.
    9. Return the last entry. For valid input exactly one entry remains: the whole decoded string.

    The solution in TypeScript

    class Solution {
    decodeString(s: string): string {
        const stack: string[] = [];
        for (const c of s) {
            if (c === '[') {
                stack.push("");
            } else if (/[a-zA-Z]/.test(c)) {
                if (stack.length === 0) {
                    stack.push("");
                }
                stack[stack.length - 1] += c;
            } else if (/[0-9]/.test(c)) {
                const top: string = stack.length > 0 ? stack[stack.length - 1] : "";
                if (!/^\d+$/.test(top)) {
                    stack.push(c);
                } else {
                    stack[stack.length - 1] += c;
                }
            } else {
                const currStr: string = stack.pop();
                const currNum: number = parseInt(stack.pop());
                const repeated: string = currStr.repeat(currNum);
                if (stack.length === 0) {
                    stack.push(repeated);
                } else {
                    stack[stack.length - 1] += repeated;
                }
            }
        }
        return stack[stack.length - 1];
    }
}

    The TypeScript details worth a closer look:

    • Counts are strings. The stack is typed string[], so a count lives on it as text such as "3". parseInt turns it into a number only when it is needed. A type annotation such as : number checks the code at compile time but converts nothing, so without parseInt the count would remain a string.
    • Regular expressions. /[a-zA-Z]/.test(c) returns true or false for one character. /^\d+$/ matches a string made only of digits, from the first character to the last, and needs at least one digit, so it fails for an empty string. That is why the empty case in the digit branch is handled without a special check.
    • repeat. "ac".repeat(3) is "acacac", and repeat(0) gives an empty string. The count is always positive here.
    • pop() can be undefined. On an empty array it returns undefined. For valid input every ] has a text entry and a count below it, and the lesson compiles without strict null checks.
    • Strings are immutable. stack[stack.length - 1] += c creates a new string and stores it back in that slot.

    Complexity

    Let n be the length of the input and m the length of the decoded output.

    Time: proportional to the input plus the output. Every input character is handled once, and each repeat builds a string of the repeated length. Text inside nested groups is copied again each time its group is folded outward, so the total work is the output size times a small factor that depends on the nesting depth. The statement keeps the output below 100,000 characters, so this is fast.

    Space: O(n + m). The stack holds counts and partial texts. Its deepest point is the nesting depth, and the buffers together never exceed the output size.

    Edge cases and common mistakes

    • No brackets. "ef" returns "ef". The empty-stack check in the letter branch is what gives the letters a place to land.
    • Multi-digit counts. "10[a]" gives ten as. Extending the top entry digit by digit keeps 10 as one count.
    • Text before a group. "a2[b]c" gives "abbc". The a sits in a buffer, then a new count starts above it because that buffer is not made of digits.
    • Nested groups with text on both sides. In "3[a2[c]]", the a must survive while the inner group is decoded, and the folded cc must be appended after it. The order of pushes and appends guarantees this.
    • Applying the count to the wrong text. The count is the entry directly under the group's text. Popping in the wrong order, count first, repeats the wrong string.
    • Forgetting parseInt. Passing a string to repeat may happen to work, because JavaScript converts it, but the conversion should be explicit and visible.

    Testing

    • "3[a]2[bc]" gives "aaabcbc".
    • "3[a2[c]]" gives "accaccacc".
    • "2[abc]3[cd]ef" gives "abcabccdcdcdef".
    • "10[a]" gives "aaaaaaaaaa".
    • "ef" gives "ef".
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free