Decode String

Published at23 Jul 2026

Stack Medium 0 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".

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.

function solution(s) {
  var countStack = []
  var resultStack = []
  var result = ''
  var 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()
      var temp = resultStack.pop()
      for (var j = 0; j < repeat; j++) temp += result
      result = temp
      i++
    } else {
      result += s[i]
      i++
    }
  }
  return 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

Gallery Stock Order Check

Harbor Cargo Lineup

Warehouse Crate Ordering

Festival Drum Echoes

Valid Parentheses Grouping

Next Greater Element

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.