Introduction

The Decode String problem involves decoding encoded strings following a specific pattern.

Encoding rule:

 k[encoded_string]

Meaning:

  • encoded_string inside brackets repeats k times

Example:

Input:3[a2[c]]

Output:
accaccacc

Explanation:

2[c] → cca + cc → acc
3[acc] → accaccacc

This problem is one of the most important applications of:

 Stack Data Structure

Constraints

1 <= s.length <= 10^5String contains:
lowercase English letters
digits
[ ]

Approach 1 : Brute Force (Recursive Expansion)

Explanations:

Explanation:

The idea is:

  • recursively decode inner brackets
  • expand repeated substrings
  • rebuild final string

Steps:

  1. Traverse string.
  2. Detect brackets.
  3. Decode inner substring.
  4. Repeat substring k times.

This approach becomes inefficient because:

  • repeated string rebuilding
  • recursion overhead
  • nested expansions

So stack-based solution is preferred.

Dry Run

Input:3[a2[c]]

Step 1:
2[c]

Output:
cc

Step 2:
a + cc

Output:
acc

Step 3:
3[acc]

Final Output:
accaccacc

Practice :

Complexity Analysis :

Time Complexity:- O(n²)Explanation :
Repeated string rebuilding may occur.

Space Complexity:- O(n)
Explanation :
Extra recursive space is used.

Approach 2 : Optimal Solution(Using Stack)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • use stack for numbers
  • use stack for strings
  • when '[' appears:
    • save current string
    • save repeat count
  • when ']' appears:
    • repeat current string
    • combine with previous string

This efficiently handles nested encoded strings.

Dry Run

Input:3[a2[c]]

Step 1:
Read 3
Count:
3

Step 2:
Push current string
Stack:
[""]

Step 3:
Read a
Current:
a

Step 4:
Read 2
Count:
2

Step 5:
Push current string
Stack:
["", "a"]

Step 6:
Read c
Current:
c

Step 7:
]

Repeat:
cc

Combine:
acc

Step 8:
]

Repeat:
accaccacc

Final Output:
accaccacc

Practice :

Complexity Analysis :

Time Complexity:- O(n)Explanation :
Each character is processed once.

Space Complexity:- O(n)
Explanation :
Stacks store intermediate strings and counts.

Why This Problem is Important

This problem builds the foundation for:

  • Stack operations
  • Nested parsing
  • String decoding
  • Expression evaluation
  • Recursive structure handling

Real-World Applications

Decode String concepts are used in:

  • File decompression
  • Data parsing
  • Compiler design
  • Markup language parsing
  • Expression interpreters

Common Beginner Mistakes

  • Forgetting multi-digit numbers
  • Incorrect stack order
  • Missing nested decoding
  • Wrong string concatenation
  • Resetting current string incorrectly

Interview Tip

Interviewers often expect:

  • proper stack usage
  • nested decoding logic
  • O(n) optimization
  • correct string handling

Always explain:

  • why stacks help manage nested structures
  • how previous strings are restored correctly

Related Questions

  • Remove Adjacent Duplicates
  • Simplify Path
  • Valid Parentheses
  • Basic Calculator
  • Mini Parser

Final Takeaway

The Decode String problem is one of the most important stack + string parsing problems.

It teaches:

  • nested structure handling
  • stack processing
  • decoding logic
  • efficient string construction

Understanding this problem builds a strong foundation for:

  • parser design
  • compiler concepts
  • advanced stack interview problems.