Decode String | LeetCode 75 | Python Stack Solution | Nested Encoding Handling |

Published: 19 March 2025
on channel: CodeVisium

181

In this LeetCode 75 problem, we are given an encoded string that follows the format k[encoded_string], where:

k is a positive integer specifying how many times the encoded_string should be repeated.
encoded_string may contain letters and can be nested inside other encoded strings.
Our task is to decode the string and return the final expanded version.
For example, given "3[a2[c]]", the correct output is "accaccacc".

Approach: Using a Stack 🏗️

To solve this problem efficiently, we use a stack-based approach. The reason a stack works well is that it helps us handle nested encodings by keeping track of intermediate states.

Step-by-Step Solution Explanation 🔍

1️⃣ Initialize Variables:

stack = [] → Used to store intermediate values (previous string state and repeat count).
curr_num = 0 → Used to track the current multiplier (k value before [).
curr_str = "" → Used to accumulate characters in the current segment.

2️⃣ Iterate Through Each Character in the String:

If the character is a digit (0-9):

Build curr_num by multiplying it by 10 and adding the current digit (to handle multi-digit numbers).
Example: "12[a]" → curr_num becomes 12.
If the character is [:

Push the current string (curr_str) and repeat count (curr_num) onto the stack.
Reset curr_str and curr_num to start a new encoded section.
If the character is ]:

Pop the last stored state (last_str, num) from the stack.
Decode the current segment by repeating curr_str num times.
Append the decoded part back to last_str.
If the character is a letter (a-z):

Simply append it to curr_str to continue building the current segment.

3️⃣ Final Result:

After processing all characters, curr_str holds the fully decoded string.

Python Code Implementation:

class Solution:
def decodeString(self, s):
stack = []
curr_num = 0
curr_str = ""

for char in s:
if char.isdigit():
curr_num = curr_num * 10 + int(char)
elif char == "[":
stack.append((curr_str, curr_num))
curr_str, curr_num = "", 0
elif char == "]":
last_str, num = stack.pop()
curr_str = last_str + num * curr_str
else:
curr_str += char

return curr_str

Example Test Cases

sol = Solution()
print(sol.decodeString("3[a]2[bc]")) # Output: "aaabcbc"
print(sol.decodeString("3[a2[c]]")) # Output: "accaccacc"
print(sol.decodeString("2[abc]3[cd]ef")) # Output: "abcabccdcdcdef"

Time & Space Complexity Analysis:
Time Complexity: O(n) 🔥

We iterate through the string once, and each character is processed at most twice (pushed/popped from stack).
Efficiently handles large strings due to linear complexity.
Space Complexity: O(n) 📦

Stack stores the intermediate states, so in the worst case (deeply nested encoding), we may store n/2 elements.

Example Walkthrough: "3[a2[c]]" 🛠️

Step 1: Stack stores intermediate states when [ appears.

char = '3' → curr_num = 3
char = '[' → stack = [("", 3)], curr_str = "", curr_num = 0
char = 'a' → curr_str = "a"
char = '2' → curr_num = 2
char = '[' → stack = [("", 3), ("a", 2)], curr_str = "", curr_num = 0
char = 'c' → curr_str = "c"
char = ']' → stack.pop() → last_str = "a", num = 2
→ curr_str = "a" + "cc" = "acc"
char = ']' → stack.pop() → last_str = "", num = 3
→ curr_str = "" + "accaccacc" = "accaccacc"

✅ Final Output: "accaccacc"

Why This Solution is Optimal? 💡

✔ Handles Nested Encodings Efficiently – Uses a stack to store previous states.
✔ Supports Multi-digit Multipliers – Correctly processes cases like "12[a]".
✔ Runs in O(n) Time – Fast and efficient for large inputs.
✔ Memory-Efficient – Uses stack space proportional to depth of nesting.

On this page of the site you can watch the video online Decode String | LeetCode 75 | Python Stack Solution | Nested Encoding Handling | with a duration of hours minute second in good quality, which was uploaded by the user CodeVisium 19 March 2025, share the link with friends and acquaintances, this video has already been watched 181 times on youtube and it was liked by 2 viewers. Enjoy your viewing!

1,612