{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Decode String – Solution & Complexity

Interview solutions
/
Decode String

Solution Walkthrough

  1. Step 1: Recursive-descent parser

    • Parse the string left to right, carrying the current index through recursive calls.
    • Accumulate multi-digit repeat counts until you reach [.
    • When a [ opens a nested group, recursively decode that group and return both the decoded substring and the index of its matching ].
    • Append the nested result repeated k times, then continue scanning from the character after ].
    def decode_string(s: str) -> str:
    def parse(i: int) -> tuple[str, int]:
        current = []
        count = 0

        while i < len(s) and s[i] != ']':
            ch = s[i]
            if ch.isdigit():
                count = count * 10 + int(ch)
                i += 1
            elif ch == '[':
                decoded, end_index = parse(i + 1)
                current.append(decoded * count)
                count = 0
                i = end_index + 1
            else:
                current.append(ch)
                i += 1

        return ''.join(current), i

    return parse(0)[0]

  2. Step 2: Iterative explicit-stack parser

    • Keep one stack for the partially built strings from outer scopes and another for the repeat counts attached to them.
    • Read digits into a multi-digit count, push (currentString, count) when you see [, and reset the current builder for the nested block.
    • When you see ], pop the previous string and repeat count, expand the current substring, and prepend it to the previous outer string.
    • This avoids recursion and cleanly handles arbitrary nesting in one left-to-right pass.
    def decode_string(s: str) -> str:
    string_stack = []
    count_stack = []
    current = ''
    count = 0

    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)
        elif ch == '[':
            string_stack.append(current)
            count_stack.append(count)
            current = ''
            count = 0
        elif ch == ']':
            repeat = count_stack.pop()
            previous = string_stack.pop()
            current = previous + current * repeat
        else:
            current += ch

    return current

FAQ

See also

Practice Decode String online (run code in the browser)Binary Tree Inorder Traversal solution (easy)Binary Tree Postorder Traversal solution (easy)Binary Tree Preorder Traversal solution (easy)Generate Parentheses solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?