Decode String

Decode a string encoded with the format k[encoded_string].

Language Selection

Choose your preferred programming language

Showing: Python

Decode String

Problem Statement

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.

Examples

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Explanation: 
- "3[a]" decodes to "aaa"
- "2[bc]" decodes to "bcbc"
- Combined: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"
Explanation: 
- "2[c]" decodes to "cc"
- "a2[c]" decodes to "acc"
- "3[acc]" decodes to "accaccacc"

Constraints

1 <= s.length <= 30
s consists of lowercase English letters, digits, and square brackets
s is a valid encoded string
1 <= k <= 300

Approach 1: Stack-Based Parsing (Optimal)

Algorithm

Use a stack to handle nested brackets and keep track of current string and repetition count.

Steps:

Use a stack to store (current_string, repetition_count) pairs
For each character:
- If digit: build the number
- If ‘[’: push current string and count to stack, reset variables
- If ‘]’: pop from stack, repeat current string, and append to previous string
- If letter: append to current string
Return the final decoded string

Implementation

Python:

def decodeString(s):
    """
    Decode string using stack-based parsing
    Time: O(n)
    Space: O(n)
    """
    stack = []
    current_string = ""
    current_num = 0
    
    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            # Push current state to stack
            stack.append((current_string, current_num))
            current_string = ""
            current_num = 0
        elif char == ']':
            # Pop from stack and repeat current string
            prev_string, repeat_count = stack.pop()
            current_string = prev_string + current_string * repeat_count
        else:
            # Regular character
            current_string += char
    
    return current_string

Java:

class Solution {
    public String decodeString(String s) {
        Stack<String> stringStack = new Stack<>();
        Stack<Integer> numStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int currentNum = 0;
        
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                currentNum = currentNum * 10 + (c - '0');
            } else if (c == '[') {
                // Push current state to stacks
                stringStack.push(currentString.toString());
                numStack.push(currentNum);
                currentString = new StringBuilder();
                currentNum = 0;
            } else if (c == ']') {
                // Pop from stacks and repeat current string
                int repeatCount = numStack.pop();
                String prevString = stringStack.pop();
                String repeatedString = currentString.toString().repeat(repeatCount);
                currentString = new StringBuilder(prevString + repeatedString);
            } else {
                // Regular character
                currentString.append(c);
            }
        }
        
        return currentString.toString();
    }
}

Go:

func decodeString(s string) string {
    var stringStack []string
    var numStack []int
    var currentString strings.Builder
    currentNum := 0
    
    for _, char := range s {
        if char >= '0' && char <= '9' {
            currentNum = currentNum*10 + int(char-'0')
        } else if char == '[' {
            // Push current state to stacks
            stringStack = append(stringStack, currentString.String())
            numStack = append(numStack, currentNum)
            currentString.Reset()
            currentNum = 0
        } else if char == ']' {
            // Pop from stacks and repeat current string
            repeatCount := numStack[len(numStack)-1]
            numStack = numStack[:len(numStack)-1]
            prevString := stringStack[len(stringStack)-1]
            stringStack = stringStack[:len(stringStack)-1]
            
            repeatedString := strings.Repeat(currentString.String(), repeatCount)
            currentString.Reset()
            currentString.WriteString(prevString + repeatedString)
        } else {
            // Regular character
            currentString.WriteRune(char)
        }
    }
    
    return currentString.String()
}

JavaScript:

function decodeString(s) {
    const stringStack = [];
    const numStack = [];
    let currentString = '';
    let currentNum = 0;
    
    for (const char of s) {
        if (char >= '0' && char <= '9') {
            currentNum = currentNum * 10 + parseInt(char);
        } else if (char === '[') {
            // Push current state to stacks
            stringStack.push(currentString);
            numStack.push(currentNum);
            currentString = '';
            currentNum = 0;
        } else if (char === ']') {
            // Pop from stacks and repeat current string
            const repeatCount = numStack.pop();
            const prevString = stringStack.pop();
            currentString = prevString + currentString.repeat(repeatCount);
        } else {
            // Regular character
            currentString += char;
        }
    }
    
    return currentString;
}

C#:

public class Solution {
    public string DecodeString(string s) {
        var stringStack = new Stack<string>();
        var numStack = new Stack<int>();
        var currentString = new StringBuilder();
        int currentNum = 0;
        
        foreach (char c in s) {
            if (char.IsDigit(c)) {
                currentNum = currentNum * 10 + (c - '0');
            } else if (c == '[') {
                // Push current state to stacks
                stringStack.Push(currentString.ToString());
                numStack.Push(currentNum);
                currentString.Clear();
                currentNum = 0;
            } else if (c == ']') {
                // Pop from stacks and repeat current string
                int repeatCount = numStack.Pop();
                string prevString = stringStack.Pop();
                string repeatedString = string.Concat(Enumerable.Repeat(currentString.ToString(), repeatCount));
                currentString.Clear();
                currentString.Append(prevString + repeatedString);
            } else {
                // Regular character
                currentString.Append(c);
            }
        }
        
        return currentString.ToString();
    }
}

Complexity Analysis

Time Complexity: O(n) - Each character is processed once
Space Complexity: O(n) - For the stacks and string building

Key Insights

Stack Approach: Use stack to handle nested brackets efficiently
State Management: Keep track of current string and repetition count
String Building: Use StringBuilder for efficient string concatenation
Bracket Matching: Handle opening and closing brackets properly

Edge Cases

Single Character: "a" → "a"
No Brackets: "abc" → "abc"
Single Repetition: "1[a]" → "a"
Nested Brackets: "3[a2[c]]" → "accaccacc"
Multiple Groups: "2[abc]3[cd]ef" → "abcabccdcdcdef"

Follow-up Questions

Different Brackets: What if you have different types of brackets?
Invalid Input: How would you handle invalid input?
Performance: How would you optimize for very large strings?
Memory Usage: How would you minimize memory usage?

Common Mistakes

Stack Management: Not properly managing stack operations
Number Parsing: Incorrectly parsing multi-digit numbers
String Concatenation: Inefficient string building
Bracket Matching: Not handling nested brackets correctly

Interview Tips

Clarify Requirements: Ask about input format and constraints
Discuss Approaches: Mention both stack and recursive approaches
Handle Edge Cases: Discuss various input scenarios
Optimize Performance: Consider time and space complexity
Explain Algorithm: Walk through the parsing process