Decode String Algorithm Solution

The decode string problem requires parsing and expanding encoded strings with nested patterns, where digits indicate repetition counts for subsequent characters or sub-patterns. This solution uses a stack-based approach to efficiently handle nested structures and complex encoding scenarios.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input string contain nested brackets? For example, 2[3[a]b]?
2. What is the maximum length of the input string? Will it be within reasonable bounds for a single pass?
3. Are we guaranteed that the input string is well-formed (balanced brackets)?
4. Should we return a single decoded string or handle multiple test cases?
5. Can the input string contain digits other than 1-9? What about letters?

Restatement in my own words: Given an encoded string following the pattern k[encoded_string], where k is a positive integer indicating how many times the encoded string should be repeated, decode the string to its fully expanded form. The decoding should handle nested structures and produce a single flattened output.

Clarification of inputs, outputs, and constraints:

• Input: A valid encoded string containing digits (1-9), letters, and brackets
• Output: The decoded string with all bracketed content properly expanded
• Constraints:
  • Input is guaranteed to be well-formed (balanced brackets)
  • Digits are only in range [1,9]
  • No empty brackets or invalid nesting

Assumptions I'm making:

• The input string will not exceed reasonable memory limits for a single pass solution
• All brackets are properly closed and nested
• The output string will not exceed reasonable length limits

Data shape and hidden structure: The input has a recursive structure where nested brackets represent repeated subproblems. Each bracketed section contains a repetition count followed by content that may itself contain nested brackets. This suggests a stack-based approach where we can process the innermost brackets first and build up to outer levels.

The problem exhibits a clear hierarchical structure where:

• Numbers indicate repetition counts
• Brackets define scope of repetition
• Letters are the terminal elements to be repeated
• Nested brackets require processing from innermost to outermost

2. Pattern Recognition

The problem exhibits a nested structure pattern with recursive repetition, which is a classic indicator of stack-based parsing or recursive descent parsing.

The key wording that signals this pattern:

• "digit followed by a substring in brackets" - This creates a clear recursive structure where numbers indicate repetition counts
• "bracketed content" - Indicates nested parsing with well-formed delimiters
• "decoded string" - Suggests a transformation process that needs to maintain proper nesting

This problem fits the stack-based parsing pattern because:

1. The structure is inherently nested (like balanced parentheses)
2. Each opening bracket creates a new parsing context
3. Each closing bracket resolves the current context and returns to parent level
4. The repetition count (digit) acts as a multiplier for the nested content

The core insight is that we need to process nested structures in LIFO (Last In, First Out) order, which makes a stack the natural data structure for this problem. When we encounter a digit followed by brackets, we're essentially creating a subproblem that needs to be solved and then repeated.

The pattern also suggests that we're dealing with string parsing with repetition, similar to problems like validating parentheses or evaluating expressions with nested structures.

This is fundamentally different from linear string manipulation problems because:

• We have to handle recursive nesting
• The repetition factor affects the entire nested structure
• We need to maintain context of what we're currently parsing

3. Approach Evolution

My first instinct is to use a stack-based approach because the nested structure of digits followed by brackets suggests we need to process innermost structures first, which is naturally handled by stacks. But that's O(n²) in worst case because for each closing bracket, we might need to process all elements in the stack. Let me think about how to optimize this.

Looking more carefully at the problem, I notice that we're dealing with a recursive structure where numbers indicate repetition counts. The key insight is that we can process this iteratively with a stack, but we need to be smarter about how we handle the repetition logic.

I notice that if I maintain a running result string and keep track of the current multiplier, I can reduce it to O(n) time by processing each character exactly once. The stack approach works, but we can avoid the nested string operations that would make it O(n²) in worst case.

Let me think about this more systematically:

• We need to parse numbers, letters, and brackets
• When we encounter a number, it tells us how many times to repeat the following content
• When we encounter '[', we start a new nested context
• When we encounter ']', we end the current context and apply repetition
• The key invariant is that at any point, we know what to repeat and how many times

The approach I'll take is to use a stack to maintain the current string being built and the repetition count. When we see a digit, we parse the full number. When we see '[', we push the current string and count onto stack, then reset. When we see ']', we pop from stack and apply the repetition to current string.

This approach gives us O(n) time complexity because we process each character once, and O(n) space for the stack in worst case where all characters are nested.

The key optimization is avoiding string concatenation operations inside nested loops by maintaining proper state tracking with the stack.

4. Data Structure Choice

For this decode string problem, I'll use a stack-based approach with two main data structures:

Primary Data Structures

1. Stack of Strings - To handle nested encodings and maintain the context of previous decoded parts
2. Stack of Integers - To store the repetition counts for each level of nesting

Why These Data Structures Are Needed

The stack approach is ideal because:

• Nested structures: When we encounter a nested encoded string like 2[abc3[def]], we need to remember the outer context (the "2" multiplier) while processing the inner part
• Backtracking capability: We need to easily return to previous states when encountering closing brackets ]
• LIFO behavior: The last opened bracket should be the first one closed, which naturally fits a stack

Time and Space Impact

• Time Complexity: O(n) where n is the length of the encoded string
• Space Complexity: O(m) where m is the maximum nesting depth, as we store at most one integer and one string per level of nesting
• Space Usage: In worst case with deeply nested structures like 100[100[100[...]]], we could have O(n) space usage

Helper Structure

I'll also use:

• StringBuilder for efficient string concatenation during the decoding process
• Character processing: Simple character-by-character parsing without additional complex structures

The stack-based approach elegantly handles the recursive nature of nested encodings while maintaining clean state management for each nesting level.

// Implementation details:
// - Stack<String> for storing previous decoded strings
// - Stack<Integer> for storing repetition counts  
// - StringBuilder for efficient string building during decoding

5. Algorithm Walkthrough

Let me trace through the algorithm with the example "3[a2[c]]":

Step 1: Process '3' - we encounter a digit, so we push the current result and multiplier onto stacks.

• Stack1 (multipliers): [1]
• Stack2 (results): [""]
• Current result: ""
• Current multiplier: 3

Step 2: Process '[' - we push current state to stacks and reset.

• Stack1: [1, 3]
• Stack2: ["", ""]
• Current result: ""
• Current multiplier: 1

Step 3: Process 'a' - append to current result.

• Current result: "a"

Step 4: Process '2' - digit found, push state and reset.

• Stack1: [1, 3, 1]
• Stack2: ["", "a"]
• Current result: ""
• Current multiplier: 2

Step 5: Process '[' - push state and reset.

• Stack1: [1, 3, 1, 2]
• Stack2: ["", "a", ""]
• Current result: ""
• Current multiplier: 1

Step 6: Process 'c' - append to current result.

• Current result: "c"

Step 7: Process ']' - we pop from stacks to finalize inner group.

• Pop multiplier: 2, result: "c"
• Current result becomes: "cc" (2 × "c")
• Pop multiplier: 3, result: "a"
• Current result becomes: "accaccacc" (3 × "acc")

Step 8: Process final ']' - pop remaining stack.

• Pop multiplier: 1, result: "accaccacc"
• Final result: "accaccacc"

The algorithm correctly handles nested structures by maintaining proper state in stacks and processes each character once, ensuring the decoded string matches the expected output.

public class DecodeString {
    public String decodeString(String s) {
        Stack<Integer> multipliers = new Stack<>();
        Stack<String> results = new Stack<>();
        StringBuilder currentResult = new StringBuilder();
        int currentMultiplier = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (Character.isDigit(c)) {
                currentMultiplier = currentMultiplier * 10 + (c - '0');
            } else if (c == '[') {
                multipliers.push(currentMultiplier);
                results.push(currentResult.toString());
                currentMultiplier = 0;
                currentResult = new StringBuilder();
            } else if (c == ']') {
                int multiplier = multipliers.pop();
                String previousResult = results.pop();
                StringBuilder newResult = new StringBuilder(previousResult);
                
                for (int j = 0; j < multiplier; j++) {
                    newResult.append(currentResult);
                }
                
                currentResult = newResult;
            } else {
                currentResult.append(c);
            }
        }
        
        return currentResult.toString();
    }
}

6. Java Solution

public class DecodeString {
    public String decodeString(String s) {
        // Use a stack to keep track of previous strings and their repetition counts
        Stack<String> stringStack = new Stack<>();
        Stack<Integer> countStack = new Stack<>();
        
        StringBuilder currentString = new StringBuilder();
        int currentCount = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (Character.isDigit(c)) {
                // Build the count number (handles multi-digit numbers)
                currentCount = currentCount * 10 + (c - '0');
            } else if (c == '[') {
                // Push current string and count to stacks
                stringStack.push(currentString.toString());
                countStack.push(currentCount);
                
                // Reset for the new nested structure
                currentString = new StringBuilder();
                currentCount = 0;
            } else if (c == ']') {
                // Pop the last string and count to repeat currentString
                String lastString = stringStack.pop();
                int repeatCount = countStack.pop();
                
                // Repeat currentString 'repeatCount' times and append to lastString
                StringBuilder repeated = new StringBuilder();
                for (int j = 0; j < repeatCount; j++) {
                    repeated.append(currentString);
                }
                
                currentString = new StringBuilder(lastString).append(repeated);
            } else {
                // Regular character, append to current string
                currentString.append(c);
            }
        }
        
        return currentString.toString();
    }
}

This solution uses two stacks to handle nested structures in the encoded string. The stack approach allows us to properly manage the hierarchical nature of the encoding where inner brackets need to be processed before outer ones. The algorithm processes each character once, making it efficient and straightforward to understand.

7. Complexity Analysis

Time Complexity: O(n) where n is the length of the encoded string.

The algorithm processes each character in the input string exactly once. While we use a stack to handle nested structures, each character is pushed and popped at most once from the stack. Therefore, the total number of operations remains linear with respect to the input size.

Space Complexity: O(m) where m is the length of the decoded string in the worst case.

In the worst-case scenario, we might need to store the entire decoded string in our result StringBuilder. Additionally, the stack can grow up to O(k) where k is the nesting depth of the encoded string. However, since we're returning a decoded string and not the intermediate stack state, the dominant space factor is the output string itself.

The solution is optimal because:

1. We must read each character at least once to decode the string
2. We must produce each decoded character at least once in our output
3. The linear time complexity matches the information-theoretic lower bound for this problem

This is near-optimal since we cannot do better than O(n) time complexity for reading and decoding a string of length n, and our space usage is directly proportional to the output size, which is unavoidable for this problem type.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty string: Should return empty string without errors
• Single character: Handle both letters and digits (e.g., "a" → "a", "3" → "3")
• Single digit followed by letter: e.g., "2a" → "aa"

Duplicate Values and Repeated States

• Nested encodings: "2[3[a]b]" requires proper handling of nested structure
• Multiple consecutive digits: "32[abc]" should parse as "32" not "3" + "2"
• Zero repetition count: "0[abc]" should produce empty string

Boundary Conditions

• Leading/trailing digits: "123abc" vs "abc123" - the former should parse as "123" + "abc"
• Invalid format: "2[a3[b]]" - nested brackets with invalid structure
• Empty brackets: "2[abc]0[]" should handle properly

Common Implementation Mistakes

• Incorrect stack management: Not properly handling nested structures when popping from stack
• Digit parsing errors: Misreading multi-digit numbers like "12" as "1" and "2"
• Index bounds: Accessing array elements beyond bounds when processing characters
• Stack overflow: Not validating input format to prevent infinite recursion or stack growth
• Incorrect bracket matching: Misidentifying closing brackets in nested structures

Implementation-specific Pitfalls

• String concatenation overhead: Using + operator in loops instead of StringBuilder
• Not handling special characters: For example, if input contains brackets in literal text rather than encoding
• Integer overflow: Parsing very large numbers that exceed integer limits

The solution must carefully validate input structure and handle all combinations of digits, letters, brackets, and nested structures to avoid runtime exceptions or incorrect decoding.

9. Alternative Approaches

There are several alternative approaches to solving the decode string problem, each with different trade-offs:

Recursive Approach with Stack: A recursive solution that processes the string character by character, using a stack to handle nested structures. This approach mirrors the natural recursive structure of the problem but requires careful handling of the recursion stack and can lead to stack overflow for deeply nested inputs.

Two-Pointer Approach: Instead of using a stack, we can use two pointers to traverse the string from left to right. This approach requires more careful index management and can be harder to reason about, especially for nested cases.

State Machine Approach: Implement a finite state machine that transitions between states like "normal text", "digit parsing", and "bracket handling". This is more complex to design but provides clean separation of concerns and can be easily extended for additional features.

StringBuilder with Manual Stack: Rather than using a dedicated stack data structure, we can simulate stack behavior using StringBuilder operations with careful index tracking. This avoids explicit stack management but requires more careful bookkeeping.

The chosen solution using a stack-based approach is preferred because it:

1. Provides clear separation between parsing and computation
2. Handles arbitrary nesting levels naturally
3. Is intuitive to understand and debug
4. Has predictable performance characteristics
5. Uses standard library collections effectively

The stack-based approach is more readable and maintainable than alternatives that require complex index tracking or state management, making it the better choice for production code in a FAANG environment.

10. Test Cases

public class DecodeStringTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic nested structure
        // Input: "3[a]2[bc]" -> Output: "aaabcbc"
        System.out.println("Test 1: " + decodeString("3[a]2[bc]"));
        
        // Test case 2: Complex nesting
        // Input: "3[a2[c]]" -> Output: "accaccacc"
        System.out.println("Test 2: " + decodeString("3[a2[c]]"));
        
        // Test case 3: Mixed content
        // Input: "2[abc]3[cd]ef" -> Output: "abcabccdcdcdef"
        System.out.println("Test 3: " + decodeString("2[abc]3[cd]ef"));
        
        // Test case 4: Single character repetition
        // Input: "1[a]" -> Output: "a"
        System.out.println("Test 4: " + decodeString("1[a]"));
        
        // Test case 5: Empty string
        // Input: "" -> Output: ""
        System.out.println("Test 5: " + decodeString(""));
        
        // Test case 6: No brackets
        // Input: "abc" -> Output: "abc"
        System.out.println("Test 6: " + decodeString("abc"));
        
        // Test case 7: Nested with numbers
        // Input: "2[2[ab]]" -> Output: "abababab"
        System.out.println("Test 7: " + decodeString("2[2[ab]]"));
        
        // Test case 8: Large number
        // Input: "10[a]" -> Output: "aaaaaaaaaa"
        System.out.println("Test 8: " + decodeString("10[a]"));
    }
}

Sample Test Cases:

Basic nested structure: "3[a]2[bc]" → "aaabcbc"

• Tests simple repetition and bracket parsing

Complex nesting: "3[a2[c]]" → "accaccacc"

• Tests nested brackets with inner repetition

Mixed content: "2[abc]3[cd]ef" → "abcabccdcdcdef"

• Tests combination of bracketed and non-bracketed content

Single character: "1[a]" → "a"

• Tests minimal case with single character repetition

Empty string: "" → ""

• Tests edge case of empty input

No brackets: "abc" → "abc"

• Tests case with no bracketed content

Deep nesting: "2[2[ab]]" → "abababab"

• Tests multiple levels of nested repetition

Large number: "10[a]" → "aaaaaaaaaa"

• Tests handling of larger repetition counts

Tricky Case:

Nested with mixed content: "2[ab3[c]]d" → "abcccabcccabccd"

• Complex case where brackets contain both letters and nested brackets with numbers

Boundary Case:

Single character with count 1: "1[a]" → "a"

• Minimal valid case that ensures proper parsing of single character repetition

11. Final Summary

The core insight is that nested bracket structures require a stack-based approach to handle proper nesting and order of operations. By processing characters sequentially and using a stack to track intermediate results, we can efficiently decode strings with arbitrary nesting levels. The solution works by maintaining the current string and multiplier at each nesting level, allowing proper handling of cases like "3[a2[c]]" → "accaccacc". This approach is optimal with O(n) time complexity and O(n) space complexity, where n is the length of the decoded string, making it efficient for all valid inputs within the given constraints.