Decode String in Python – Step-by-Step LeetCode75 Solution

Decoding strings with nested patterns is a common problem in coding interviews, competitive programming, and real-world applications. The Decode String problem on LeetCode challenges you to expand strings encoded in the format k[encoded_string] including nested and multi-digit repetitions. Mastering this problem sharpens your skills in stack operations, string manipulation and algorithmic thinking, making it a must-solve for Python developers and aspiring software engineers.

In this blog, we’ll provide a complete Python solution followed by a step-by-step explanation to help you decode any string efficiently.

Problem Statement

You are given an encoded string s. The encoding rule is:

• k[encoded_string], where encoded_string is repeated exactly k times.
• k is always a positive integer.
• Nested encodings like "3[a2[c]]" are possible.

Your task: Decode the string and return the final decoded result.

Understanding the Problem

Consider the string:

s = "3[a2[c]]"

Decoding steps:

1. "2[c]" → "cc"
2. "a2[c]" → "acc"
3. "3[a2[c]]" → "accaccacc"

A stack-based approach is ideal because it allows handling nested brackets efficiently.

Complete Python Solution

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        current_num = 0
        current_str = ""

        for char in s:
            if char.isdigit():
                current_num = current_num * 10 + int(char)
            elif char == '[':
                stack.append((current_num, current_str))
                current_num = 0
                current_str = ""
            elif char == ']':
                num, prev_str = stack.pop()
                current_str = prev_str + current_str * num
            else:
                current_str += char

        return current_str

Step-by-Step Explanation

Step 1: Initialize Variables

We use:

• stack to store (repeat_count, previous_string) tuples.
• current_num to build multi-digit numbers.
• current_str to accumulate the current substring.

stack = []
current_num = 0
current_str = ""

Step 2: Traverse the String

Loop through each character of the string:

for char in s:
    # logic for digits, brackets, or letters will go here

Step 3: Handle Digits

If a character is a digit, update current_num to handle numbers like "10[a]":

if char.isdigit():
    current_num = current_num * 10 + int(char)

Step 4: Handle Opening Brackets '['

Push the current number and string to the stack, then reset them:

elif char == '[':
    stack.append((current_num, current_str))
    current_num = 0
    current_str = ""

Step 5: Handle Closing Brackets ']'

Pop from the stack and repeat the substring:

elif char == ']':
    num, prev_str = stack.pop()
    current_str = prev_str + current_str * num

This ensures that inner brackets are expanded first, handling nested structures correctly.

Step 6: Handle Letters

Add letters directly to the current string:

else:
    current_str += char

Step 7: Return the Decoded String

After traversing the string, current_str contains the final result:

return current_str

Time & Space Complexity

• Time Complexity: O(n * k) — Each character may be processed multiple times when repeating substrings.
• Space Complexity: O(n) — Stack stores previous strings and numbers.

Edge Cases

Input	Output	Explanation
"3[a]"	"aaa"	Single repetition
"10[a]"	"aaaaaaaaaa"	Multi-digit number
"2[3[a]b]"	"aaabaaab"	Nested brackets
"abc3[cd]xyz"	"abccdcdcdxyz"	Letters outside brackets

Real-World Applications

1. Text Compression & Decompression – Similar to run-length encoding.
2. Code Parsing – Decoding nested structures in compilers or interpreters.
3. Data Transformation – Expanding repeated patterns in datasets.
4. Gaming & Simulations – Handling repeated scripted instructions or levels.

Conclusion

The Decode String problem is an excellent way to master stack-based algorithms and advanced string manipulation in Python. By carefully handling digits, letters, and nested brackets, you can efficiently decode even the most complex patterns. Practicing this problem enhances your algorithmic thinking, coding precision and problem-solving skills, making it invaluable for coding interviews, competitive programming and real-world applications where structured data processing is essential.

Moreover, understanding this approach lays a strong foundation for tackling other nested or recursive problems. It improves your ability to design efficient solutions, handle complex data structures and implement robust scalable code in Python. Mastering such problems not only boosts your confidence as a programmer but also prepares you to solve a wide range of practical challenges in software development and data processing.

Related Reads

• 500 + AI, Machine Learning, Deep Learning, Computer Vision and NLP Projects with Code
• SkyPilot: Simplifying AI Workload Management Across Any Infrastructure
• Motia: The Unified Backend Framework That Eliminates Runtime Fragmentation
• MLOps-Basics: A Step-by-Step Guide to Mastering Machine Learning Operations
• LLaMA-Factory: Simplifying Fine-Tuning for 100+ Large Language and Vision Models

References

Decode String Problem – Master stack-based algorithms and handle nested string patterns efficiently.

Stack-Based Algorithms – Learn how stacks simplify parsing and problem-solving.

String Manipulation in Python – Improve your ability to process and transform complex strings.

Nested or Recursive Problems – Build a strong foundation to tackle complex recursive or nested data structures.