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 105.
Example 1:
Input: s = "3[a]2[bc]" Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]" Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef" Output: "abcabccdcdcdef"
Constraints:
1 <= s.length <= 30s consists of lowercase English letters, digits, and square brackets '[]'.s is guaranteed to be a valid input.s are in the range [1, 300].The key challenge in Decode String is handling nested patterns such as k[encoded_string], where the substring inside brackets must be repeated k times. Since these patterns can appear recursively, a structured way to process them is required.
A common strategy is using a stack-based approach. As you iterate through the string, push intermediate strings and repetition counts when encountering an opening bracket [. When a closing bracket ] appears, pop the last stored context, repeat the decoded substring accordingly, and append it to the previous string segment.
Another effective method is recursion, where each recursive call processes a bracketed substring and returns the decoded portion to its parent call. Both approaches naturally handle nested structures.
Because each character is processed a limited number of times, the overall complexity remains linear with respect to the input size, while auxiliary space is used to store intermediate results.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-Based Parsing | O(n) | O(n) |
| Recursive Decoding | O(n) | O(n) |
NeetCode
This approach uses a stack to decode the string iteratively. Each time we encounter a '[', we push the current accumulated string and the current repetition number to the stack. When we encounter a ']', we pop from the stack, retrieve the last accumulated string and repeat the current decoded substring accordingly.
Time Complexity: O(n), where n is the length of the input string, since we scan through the string linearly while utilizing stack operations.
Space Complexity: O(n), due to the stacks used to keep track of numbers and strings.
1import java.util.Stack;
2
3public class DecodeString {
4 public static String decodeString(String s) {
5
This Java solution uses two stacks: one for numbers to handle the multiplicative factor and another for strings to store the current result. The encoded string is parsed character by character, with updates to the current partially decoded string based on characters, '[' or ']', and numbers encountered.
This approach uses recursion to decode the string. The function processes the string, and upon encountering a '[', it recursively decodes the repeating substring. This allows elegant handling of nested encoded strings by delegating responsibility to sub-problems.
Time Complexity: O(n), with n as length of string, since recursive steps are based on string length.
Space Complexity: O(n), mainly for recursive call stack and intermediate storage.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Decode String is a well-known interview problem and has appeared in interviews at major tech companies. It tests understanding of stacks, recursion, and string parsing with nested structures.
Yes, recursion is another popular approach. Each recursive call processes the substring inside brackets and returns the decoded result to the previous level, naturally handling nested structures.
A stack is the most commonly used data structure for this problem. It helps store the current string state and repetition counts when encountering brackets, making it easy to reconstruct nested decoded segments.
The optimal approach typically uses a stack to track numbers and partial strings while traversing the input. When a closing bracket is encountered, the current substring is repeated and appended to the previous context. This efficiently handles nested patterns in linear time.
This JavaScript recursive solution utilizes inner functions to address deep or nested encoding repetitions, systematically appending the assembled decoded expansion upon hitting closing brackets, ultimately integrating into the overarching decodable pattern.