Decode String Problem: Mastering Stacks for Nested String Parsing

1️⃣ Understanding the Problem

The Decode String problem asks us to decode a string like 3[a2[c]] into accaccacc

Format: k[encoded_string] means repeat encoded_string k times.

Nesting: Strings can have nested patterns (e.g., 3[a2[c]]).

Why is this relevant?

👉 It mimics real-world scenarios like:

• Data Compression (eg: run-length encoding).
• Parsing Nested Structures (JSON, HTML tags, compiler syntax).
• Algorithm Design (stack-based approaches).

Input Example: 3[a2[c]]
Output: "accaccacc"

Rules:

k[encoded_str] → Repeat encoded_str k times.

Can be nested (e.g., 2[3[a]b] → aaabaaab).

Key Observations:

1. Numbers (k) can be multi-digit (e.g., 10[a]).
2. Brackets ([ ]) define nested scopes.
3. Order Matters: Inner brackets must be resolved first (like math parentheses).

Identifying the Need for Stacks

Why Stacks?

Last-In-First-Out (LIFO) matches nested structures.

State Management:

1. When we see [, save current progress (like pausing a loop).
2. When we see ], resume from the saved state.

Analogy:

• Like undo/redo in apps—stacks remember "where you left off."

Designing the Stack-Based Algorithm

Data Structures Needed:

countStack: Stores numbers (k) before [.
stringStack: Stores partial strings before [.
currentString: Builds the result incrementally.
currentNum: Accumulates multi-digit numbers.

Algorithm Steps:

1. Loop through each character (char):
2. If char is a digit:
3. Update currentNum (e.g., "12" → 12).
4. If char is [:
5. Push currentNum to countStack.
6. Push currentString to stringStack.
7. Reset currentNum and currentString.
8. If char is ]:
9. Pop countStack for k.
10. Pop stringStack for prevString.
11. Update currentString = prevString + (currentString repeated k times).
12. Else (letter):
13. Append char to currentString.
14. Return currentString (fully decoded).

Let's take the string  and see how the algorithm works:

3[a2[c]]

Initialize:

currentString = ''
currentNumber = 0
countStack = []
stringStack = []

1. Iterate through each character:

'3': It's a digit, so currentNumber = 3.

'[':
  Push currentNumber (3) to countStack.
  Push currentString ('') to stringStack.
  Reset currentNumber = 0 and currentString = ''.

'a': It's a letter, so currentString = 'a'.
'2': It's a digit, so currentNumber = 2.

'[':
  Push currentNumber (2) to countStack.
  Push currentString ('a') to stringStack.
  Reset currentNumber = 0 and currentString = ''.

'c': It's a letter, so currentString = 'c'.

']':
  Pop countStack (2) 
  Pop stringStack ('a').
  currentString = 'a' + 'c'.repeat(2) = 'a' + 'cc' = 'acc'.

']':
  Pop countStack (3) 
  Pop stringStack ('').
  currentString = '' + 'acc'.repeat(3) = 'accaccacc'.

Final currentString is 'accaccacc'.

Why Stacks Work:

1. Stacks help us remember the context when we encounter a nested [. We save the current string and number, then start fresh inside the new [.
2. When we see ], we use the saved number and string to build the current string correctly, considering the nesting.

let currentNum = 0

let currentString = ""

let countStack = []

let stringStack = []

1️⃣ Understanding the Problem

The Decode String problem asks us to decode a string like 3[a2[c]] into accaccacc

Format: k[encoded_string] means repeat encoded_string k times.

Nesting: Strings can have nested patterns (e.g., 3[a2[c]]).

Why is this relevant?

👉 It mimics real-world scenarios like:

• Data Compression (eg: run-length encoding).
• Parsing Nested Structures (JSON, HTML tags, compiler syntax).
• Algorithm Design (stack-based approaches).

Input Example: 3[a2[c]]
Output: "accaccacc"

Rules:

k[encoded_str] → Repeat encoded_str k times.

Can be nested (e.g., 2[3[a]b] → aaabaaab).

Key Observations:

1. Numbers (k) can be multi-digit (e.g., 10[a]).
2. Brackets ([ ]) define nested scopes.
3. Order Matters: Inner brackets must be resolved first (like math parentheses).

Identifying the Need for Stacks

Why Stacks?

Last-In-First-Out (LIFO) matches nested structures.

State Management:

1. When we see [, save current progress (like pausing a loop).
2. When we see ], resume from the saved state.

Analogy:

• Like undo/redo in apps—stacks remember "where you left off."

Designing the Stack-Based Algorithm

Data Structures Needed:

countStack: Stores numbers (k) before [.
stringStack: Stores partial strings before [.
currentString: Builds the result incrementally.
currentNum: Accumulates multi-digit numbers.

Algorithm Steps:

1. Loop through each character (char):
2. If char is a digit:
3. Update currentNum (e.g., "12" → 12).
4. If char is [:
5. Push currentNum to countStack.
6. Push currentString to stringStack.
7. Reset currentNum and currentString.
8. If char is ]:
9. Pop countStack for k.
10. Pop stringStack for prevString.
11. Update currentString = prevString + (currentString repeated k times).
12. Else (letter):
13. Append char to currentString.
14. Return currentString (fully decoded).

Let's take the string  and see how the algorithm works:

3[a2[c]]

Initialize:

currentString = ''
currentNumber = 0
countStack = []
stringStack = []

1. Iterate through each character:

'3': It's a digit, so currentNumber = 3.

'[':
  Push currentNumber (3) to countStack.
  Push currentString ('') to stringStack.
  Reset currentNumber = 0 and currentString = ''.

'a': It's a letter, so currentString = 'a'.
'2': It's a digit, so currentNumber = 2.

'[':
  Push currentNumber (2) to countStack.
  Push currentString ('a') to stringStack.
  Reset currentNumber = 0 and currentString = ''.

'c': It's a letter, so currentString = 'c'.

']':
  Pop countStack (2) 
  Pop stringStack ('a').
  currentString = 'a' + 'c'.repeat(2) = 'a' + 'cc' = 'acc'.

']':
  Pop countStack (3) 
  Pop stringStack ('').
  currentString = '' + 'acc'.repeat(3) = 'accaccacc'.

Final currentString is 'accaccacc'.

Why Stacks Work:

1. Stacks help us remember the context when we encounter a nested [. We save the current string and number, then start fresh inside the new [.
2. When we see ], we use the saved number and string to build the current string correctly, considering the nesting.

let currentNum = 0
let currentString = ""
let countStack = []
let stringStack = []

let i = 0

for (let char of s) {

if (!isNaN(char)) { // if a number
currentNum = currentNum * 10 + parseInt(char)
}

else if (char === '[') {
  countStack.push(currentNum)
  stringStack.push(currentString)
  currentNum = 0
  currentString = ""
}   

else if (char === ']') {
  let num = countStack.pop()
  let prevString = stringStack.pop()
  currentString = prevString + currentString.repeat(num)
} 

else {
  currentString += char
}

}

return currentString

};