Decode String - Practice Coding Problems

Decode String - Problem

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k.

For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 10⁵.

Input & Output

Example 1 — Nested Brackets

$ Input: s = "3[a2[c]]"

› Output: "accaccacc"

💡 Note: First decode inner pattern: 2[c] → "cc", then 3[acc] → "accaccacc"

Example 2 — Sequential Patterns

$ Input: s = "2[bc]3[cd]ef"

› Output: "bcbccdcdcdef"

💡 Note: Decode 2[bc] → "bcbc", then 3[cd] → "cdcdcd", combine with "ef" → "bcbccdcdcdef"

Example 3 — Simple Pattern

$ Input: s = "abc3[cd]xyz"

› Output: "abccdcdcdxyz"

💡 Note: Keep "abc", decode 3[cd] → "cdcdcd", append "xyz" → "abccdcdcdxyz"

Constraints

1 ≤ s.length ≤ 30
s consists of lowercase English letters, digits, and square brackets '[]'
s is guaranteed to be a valid input
All the integers in s are in the range [1, 300]

Visualization

Tap to expand

Understanding the Visualization

Input

Encoded string with nested bracket patterns

Process

Decode from innermost brackets outward

Output

Fully expanded decoded string

Key Takeaway

🎯 Key Insight: Use a stack or recursion to handle nested patterns by processing from innermost brackets outward

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to process nested brackets from inside out, either using a stack to track state or recursion to handle nesting naturally. The stack approach is most efficient with O(n) time and O(n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Stack Approach	O(n)	O(n)	Use two stacks to track current string and repeat counts as we traverse the input
Brute Force - String Replacement	O(n²)	O(n²)	Repeatedly find and replace the innermost bracket patterns until none remain
Recursive with Memoization	O(n)	O(n)	Use recursion to decode nested patterns with memoization to avoid recomputing

Stack Approach — Algorithm Steps

Initialize two stacks for strings and counts
Traverse character by character
Push to stacks when encountering '['
Pop and repeat when encountering ']'

Visualization

Tap to expand

Step-by-Step Walkthrough

Push State

When '[' found, save current state to stacks

Build String

Continue building current string

Pop & Repeat

When ']' found, pop and repeat current string

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

char* solution(char* s) {
    char stackStr[100][1001];
    int stackNum[100];
    int stackTop = -1;
    char* currentStr = malloc(10001 * sizeof(char));
    currentStr[0] = '\0';
    int currentNum = 0;
    
    for (int i = 0; i < strlen(s); i++) {
        char ch = s[i];
        if (isdigit(ch)) {
            currentNum = currentNum * 10 + (ch - '0');
        } else if (ch == '[') {
            stackTop++;
            strcpy(stackStr[stackTop], currentStr);
            stackNum[stackTop] = currentNum;
            currentStr[0] = '\0';
            currentNum = 0;
        } else if (ch == ']') {
            char* prevStr = stackStr[stackTop];
            int num = stackNum[stackTop];
            stackTop--;
            
            char* repeated = malloc(10001 * sizeof(char));
            strcpy(repeated, prevStr);
            for (int j = 0; j < num; j++) {
                strcat(repeated, currentStr);
            }
            strcpy(currentStr, repeated);
            free(repeated);
        } else {
            int len = strlen(currentStr);
            currentStr[len] = ch;
            currentStr[len + 1] = '\0';
        }
    }
    
    return currentStr;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through input string, each character processed once

✓ Linear Growth

Space Complexity

O(n)

Two stacks store at most O(n) elements for nested patterns

⚡ Linearithmic Space

78.5K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler