Decode String

Published at23 Jul 2026

Stack Medium 3 views

Like0

You are given an encoded string following the pattern k[encoded_string], where k is a positive integer indicating how many times the content inside the brackets should be repeated. The brackets can be nested, meaning you must decode the innermost brackets first.

Two stacks provide a clean solution: one stack for repeat counts and one stack for partial results. When you encounter a number, build the full count. When you encounter [, push the current count and current decoded string onto their stacks, then reset both. When you encounter ], pop the count and previous string, repeat the current decoded string count times, and append it to the previous string.

For example, "3[a]2[bc]"→"aaabcbc". "3[a2[c]]"→ inner 2[c] becomes "cc", then 3[acc]→"accaccacc".The two-stack approach elegantly handles nesting. The count stack tracks how many times to repeat the current decoded string. The result stack saves progress from outer brackets while inner brackets are being processed.When a [ is encountered, the current result is pushed onto the result stack and reset. This saves the context of the outer level while the inner level is processed. When ] is encountered, the count is popped, the current result is repeated, and the previous result from the stack is prepended.This pattern of using two stacks to handle nested structures is common in parsing problems. The same technique applies to decoding JSON-like structures or evaluating nested arithmetic expressions.Be careful with multi-digit numbers like 12[a] or 100[b]. The number parsing loop must accumulate all consecutive digits before the opening bracket.

Example Input & Output

Example 1

Input

3[a2[c]]

Output

accaccacc

Explanation

Inner 2[c] = cc. Outer 3[acc] = accaccacc.

Example 2

Input

2[abc]3[cd]ef

Output

abcabccdcdcdef

Explanation

2[abc]=abcabc, 3[cd]=cdcdcd, then +ef.

Example 3

Input

3[a]2[bc]

Output

aaabcbc

Explanation

3[a] = aaa, 2[bc] = bcbc. Combined: aaabcbc.

Example 4

Input

abc3[cd]xyz

Output

abccdcdcdxyz

Explanation

3[cd]=cdcdcd inserted between abc and xyz.

Algorithm Flow

Recommendation Algorithm Flow for Decode String

Solution Approach

Use two stacks:countStack and resultStack. Iterate through each character. If it's a digit, build the full number. If it's [, push the current count and current result, then reset both. If it's ], pop count and previous result, repeat the current result count times, and append to previous. Otherwise, it's a letter, append to current result.

Time complexity is O(n * k) where k is the max repeat count. Space complexity is O(n) for the stacks.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public String solution(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<String> resultStack = new Stack<>();
        String result = "";
        int i = 0;
        while (i < s.length()) {
            char ch = s.charAt(i);
            if (ch >= '0' && ch <= '9') {
                int num = 0;
                while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    num = num * 10 + (s.charAt(i) - '0'); i++;
                }
                countStack.push(num);
            } else if (ch == '[') { resultStack.push(result); result = ""; i++; }
            else if (ch == ']') {
                int repeat = countStack.pop();
                String temp = resultStack.pop();
                for (int j = 0; j < repeat; j++) temp += result;
                result = temp; i++;
            } else { result += ch; i++; }
        }
        return result;
    }
}

javascript

function solution(s) {
  var countStack = [], resultStack = [], result = '', i = 0;
  while (i < s.length) {
    if (s[i] >= '0' && s[i] <= '9') {
      var num = 0;
      while (i < s.length && s[i] >= '0' && s[i] <= '9') { num = num * 10 + Number(s[i]); i++; }
      countStack.push(num);
    } else if (s[i] === '[') { resultStack.push(result); result = ''; i++; }
    else if (s[i] === ']') {
      var repeat = countStack.pop(), temp = resultStack.pop();
      for (var j = 0; j < repeat; j++) temp += result;
      result = temp; i++;
    } else { result += s[i]; i++; }
  }
  return result;
}

php

<?php
function solution($s) {
    $countStack = []; $resultStack = []; $result = ''; $i = 0;
    while ($i < strlen($s)) {
        if ($s[$i] >= '0' && $s[$i] <= '9') {
            $num = 0;
            while ($i < strlen($s) && $s[$i] >= '0' && $s[$i] <= '9') { $num = $num * 10 + intval($s[$i]); $i++; }
            array_push($countStack, $num);
        } elseif ($s[$i] == '[') { array_push($resultStack, $result); $result = ''; $i++; }
        elseif ($s[$i] == ']') {
            $repeat = array_pop($countStack); $temp = array_pop($resultStack);
            for ($j = 0; $j < $repeat; $j++) $temp .= $result;
            $result = $temp; $i++;
        } else { $result .= $s[$i]; $i++; }
    }
    return $result;
}

python

def solution(s):
    count_stack = []
    result_stack = []
    result = ''
    i = 0
    while i < len(s):
        if s[i].isdigit():
            num = 0
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i]); i += 1
            count_stack.append(num)
        elif s[i] == '[':
            result_stack.append(result); result = ''; i += 1
        elif s[i] == ']':
            repeat = count_stack.pop(); temp = result_stack.pop()
            for _ in range(repeat): temp += result
            result = temp; i += 1
        else:
            result += s[i]; i += 1
    return result

rust

fn solution(s: &str) -> String {
    let mut count_stack: Vec<i32> = Vec::new();
    let mut result_stack: Vec<String> = Vec::new();
    let mut result = String::new();
    let chars: Vec<char> = s.chars().collect();
    let mut i = 0;
    while i < chars.len() {
        if chars[i].is_digit(10) {
            let mut num = 0;
            while i < chars.len() && chars[i].is_digit(10) { num = num * 10 + (chars[i] as i32 - 48); i += 1; }
            count_stack.push(num);
        } else if chars[i] == '[' { result_stack.push(result.clone()); result.clear(); i += 1; }
        else if chars[i] == ']' {
            let repeat = count_stack.pop().unwrap();
            let mut temp = result_stack.pop().unwrap();
            for _ in 0..repeat { temp += &result; }
            result = temp; i += 1;
        } else { result.push(chars[i]); i += 1; }
    }
    result
}

typescript

function solution(s: string): string {
    var countStack: number[] = [], resultStack: string[] = [], result = '', i = 0;
    while (i < s.length) {
        if (s[i] >= '0' && s[i] <= '9') {
            var num = 0;
            while (i < s.length && s[i] >= '0' && s[i] <= '9') { num = num * 10 + Number(s[i]); i++; }
            countStack.push(num);
        } else if (s[i] === '[') { resultStack.push(result); result = ''; i++; }
        else if (s[i] === ']') {
            var repeat = countStack.pop() as number, temp = resultStack.pop() as string;
            for (var j = 0; j < repeat; j++) temp += result;
            result = temp; i++;
        } else { result += s[i]; i++; }
    }
    return result;
}

Related Stack Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Decode String

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Stack Challenges

Largest Rectangle in Histogram

Trapping Rain Water

Longest Valid Parentheses

Count Binary Substrings

Implement Stack Using Queues

Make The String Great

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.