Decode String

115.1k
0

Given an encoded string s, return the decoded string.

The encoding format is k[encoded_string], where encoded_string inside the brackets must be repeated exactly k times. The integer k is always positive. The input is always valid, brackets are balanced, and digits appear only as repeat counts before brackets.

Example 1

Input: s = "3[a2[c]]"
Output: "accaccacc"
Explanation: The inner pattern 2[c] becomes "cc". The outer pattern becomes 3[acc], so the decoded string is "accaccacc".

Example 2

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Explanation: The pattern 2[abc] becomes "abcabc", the pattern 3[cd] becomes "cdcdcd", and the trailing "ef" stays unchanged.

Approach 1: Recursive Parsing

Nested brackets contain smaller encoded parts. Decoding must begin from the innermost bracket because the outer repeat count needs the fully decoded inner string.

Recursion works well because every bracketed part follows the same decoding process. A helper function decodes one section at a time and stops after finding a closing bracket.

The main function starts decoding from index 0. Every recursive call returns the decoded text and the position where decoding stopped.

Algorithm

  • Create a helper function solve(index) to decode the string from the given index.

  • Continue reading characters until the end of the string or a closing bracket ] appears.

  • Read all consecutive digits and build the complete repeat count, such as 12 or 100.

  • Skip the opening bracket [ after reading the repeat count.

  • Call solve(index) again to decode the complete text inside the brackets.

  • Add the decoded bracket text to the result according to the repeat count.

  • Add every normal lowercase letter directly to the current result.

  • Return the decoded result and the current index after completing the current bracket section.

Dry Run

Decode String Approach 1

Decode String Approach 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Decodes until a closing bracket or string end.
pair<string, int> solve(string &s, int index) {
string result = "";
int n = s.size();
// Process until the current segment ends.
while (index < n && s[index] != ']') {
// A digit starts the repeat count.
if (isdigit(s[index])) {
int repeatCount = 0;
// Build the complete multi-digit count.
while (index < n && isdigit(s[index])) {
repeatCount = repeatCount * 10 + (s[index] - '0');
index++;
}
// Move past the opening bracket.
index++;
// Decode the inner segment.
pair<string, int> innerData = solve(s, index);
string innerString = innerData.first;
index = innerData.second;
// Move past the closing bracket.
index++;
// Repeat the decoded inner segment.
for (int count = 0; count < repeatCount; count++) {
result += innerString;
}
}
else {
// Add the letter to the current segment.
result += s[index];
index++;
}
}
// Return the segment and boundary index.
return {result, index};
}
public:
// Decodes a valid encoded string.
string decodeString(string s) {
pair<string, int> decodedData = solve(s, 0);
return decodedData.first;
}
};
// Driver code
int main() {
string s = "3[a2[c]]";
Solution obj;
cout << obj.decodeString(s);
return 0;
}

Complexity Analysis

Time Complexity: O(N + M), where n is the encoded string length and M is the decoded string length. Each encoded character is scanned once, and generated characters are appended to the answer.

Space Complexity: O(M + D), where M is the decoded string length and D is the maximum nesting depth. The decoded output dominates storage, and recursive calls add recursive stack space for nested brackets.

Approach 2: Stack Parsing

Process the encoded string from left to right. Every character can be handled as follows:

  • Letter: Add to currentString.

  • Digit: Build currentCount.

  • Opening bracket [: Save currentString and currentCount.

  • Closing bracket ]: Restore the saved values and repeat the completed segment.

Nested segments require restoring the most recently saved values first, so two stacks are used: one for repeat counts and one for previous strings.

Algorithm

  • Initialize countStack, stringStack, currentString, and currentCount.

  • Traverse every character from left to right.

  • For a digit, update currentCount to support multi-digit numbers.

  • For a letter, append the letter to currentString.

  • For [, push currentCount and currentString into the respective stacks, then reset both values.

  • For ], pop the saved count and prefix, repeat currentString, and combine both parts.

  • Return currentString after complete traversal.

Dry Run

Decode String Approach 2

Decode String Approach 2

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Decodes the string using stacks.
string decodeString(string s) {
stack<int> countStack;
stack<string> stringStack;
string currentString = "";
int currentCount = 0;
// Process each symbol once.
for (int index = 0; index < s.size(); index++) {
char ch = s[index];
// Build the repeat count.
if (isdigit(ch)) {
currentCount = currentCount * 10 + (ch - '0');
}
else if (ch == '[') {
// Save the current context.
countStack.push(currentCount);
stringStack.push(currentString);
// Reset for the nested segment.
currentCount = 0;
currentString = "";
}
else if (ch == ']') {
// Restore the saved count and prefix.
int repeatCount = countStack.top();
countStack.pop();
string previousString = stringStack.top();
stringStack.pop();
string repeatedString = "";
// Repeat the completed segment.
for (int count = 0; count < repeatCount; count++) {
repeatedString += currentString;
}
// Join the prefix and repeated segment.
currentString = previousString + repeatedString;
}
else {
// Add the letter to the current segment.
currentString += ch;
}
}
// Return the fully decoded string.
return currentString;
}
};
// Driver code
int main() {
string s = "3[a2[c]]";
Solution obj;
cout << obj.decodeString(s);
return 0;
}

Complexity Analysis

Time Complexity: O(N + M), where N is the encoded string length and M is the decoded string length. Each encoded character is inspected once, and every decoded character is produced once.

Space Complexity: O(M + D), where M is the decoded string length and D is the maximum nesting depth. The stacks store one context per active bracket level, and the decoded answer stores generated characters.

FAQs

Q1. Can the repeat count contain more than one digit?
Yes. Consecutive digits form one complete number, so 12[a] produces twelve copies of "a".

Q2. Why does a stack help in Decode String?
A stack saves the decoding state before a nested bracket begins. The latest unfinished bracket must finish first, so stack order matches nested decoding.

Q3. Why does the complexity use decoded length m?
The decoded output can be much longer than the encoded input. Creating the final result requires processing every decoded character, so the complexity depends on m.

Q4. Does the stack approach handle adjacent patterns such as 2[ab]3[c]?
Yes. Each completed segment joins the decoded prefix, and traversal then continues with the next pattern.

Q5. Why is the maximum nesting depth D ≤ N/2?
Every nesting level needs one opening bracket [ and one closing bracket ]. Therefore, D levels need at least 2D characters, so the maximum depth cannot exceed N/2.

Stack

Read Similar Blogs

Stack

Sum of Subarray Ranges

Input: nums = [1, 2, 3] Output: 4 Explanation: The subarrays are [1] , [2] , [3] , [1, 2] , [2, 3] , and [1, 2, 3] . Their corresponding ranges are 0 , 0 , 0 , 1 , 1 , and 2 . The sum of all subarr...

86.7k
Stack

Introduction to Stack

Imagine a stack of plates in a kitchen. Whenever you add a new plate, you place it on the top. When you need a plate, you also take it from the top. You never remove a plate from the...

69.3k
Two PointerStackString

Reverse Every Word in a String

Given a string s , reverse every word individually. The spaces should remain in the same positions, and the order of words should not change. A word is a continuous group of non-space characters. I...

83.2k
Comments0