394. Decode String

Description

The problem requires decoding a string that is encoded in a specific format. The format is such that each group of encoded characters is represented as k[encoded_string], where k is the number of times the encoded_string should be repeated. The task is to decode the string according to these rules.

Intuition

The problem can be intuitively solved using a stack data structure, which helps to manage nested and sequential decoding processes. The stack stores characters and numbers as we traverse the string. When we encounter a closing bracket (]), it signals that we have reached the end of an encoded part, and the characters stored in the stack can be processed and decoded accordingly.

Approach

1. Stack Utilization: Traverse through each character in the string: - If the character is not a closing bracket (]), push it onto the stack. - When encountering a closing bracket: - Pop characters from the stack until an opening bracket ([) is found, forming the encoded_string. - Pop the digits (representing k) and convert them to an integer. - Repeat the encoded_string k times and push the result back onto the stack.
2. Building the Result: After processing the entire string, the stack will contain the decoded characters in order. Pop elements from the stack to form the final decoded string.

Complexity

Time Complexity:

The time complexity is O(n), where n is the length of the string. Each character is processed and added to the stack only once.

Space Complexity:

The space complexity is O(n) as we may store all characters in the stack in the worst case.

Code

C++

class Solution {
public:
    string decodeString(string s) {
        stack st;
        
        for(char ch : s) {
            if(ch != ']') {
                st.push(ch);
                continue;
            }
            
            string innerString = "";
            while(!st.empty() && st.top() != '[') {
                innerString = st.top() + innerString;
                st.pop();
            }
            st.pop(); // Pop '['
            
            string multiplierStr = "";
            while(!st.empty() && isdigit(st.top())) {
                multiplierStr = st.top() + multiplierStr;
                st.pop();
            }
            
            int multiplier = stoi(multiplierStr);
            string repeatedString = "";
            for(int i = 0; i < multiplier; ++i) {
                repeatedString += innerString;
            }
            
            for(char c : repeatedString) {
                st.push(c);
            }
        }
        
        string result = "";
        while(!st.empty()) {
            result = st.top() + result;
            st.pop();
        }
        
        return result;
    }
};

Python

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        
        for char in s:
            if char != ']':
                stack.append(char)
                continue
            
            innerString = ""
            while stack and stack[-1] != '[':
                innerString = stack.pop() + innerString
            stack.pop() # Pop '['
            
            multiplier = ""
            while stack and stack[-1].isdigit():
                multiplier = stack.pop() + multiplier
            
            stack.append(int(multiplier) * innerString)
        
        return ''.join(stack)

Java

class Solution {
    public String decodeString(String s) {
        Stack stack = new Stack<>();
        
        for(char ch : s.toCharArray()) {
            if(ch != ']') {
                stack.push(ch);
                continue;
            }
            
            StringBuilder innerString = new StringBuilder();
            while(!stack.isEmpty() && stack.peek() != '[') {
                innerString.insert(0, stack.pop());
            }
            stack.pop(); // Pop '['
            
            StringBuilder multiplierStr = new StringBuilder();
            while(!stack.isEmpty() && Character.isDigit(stack.peek())) {
                multiplierStr.insert(0, stack.pop());
            }
            
            int multiplier = Integer.parseInt(multiplierStr.toString());
            String repeatedString = innerString.toString().repeat(multiplier);
            
            for(char c : repeatedString.toCharArray()) {
                stack.push(c);
            }
        }
        
        StringBuilder result = new StringBuilder();
        while(!stack.isEmpty()) {
            result.insert(0, stack.pop());
        }
        
        return result.toString();
    }
}

JavaScript

var decodeString = function(s) {

    const stack = []
    for(const char of s) {
        if(char !== "]") {
            stack.push(char)
            continue
        }
        let currentChar = stack.pop()
        let innerString = ""
        while(currentChar !== "[") {
            innerString = currentChar + innerString
            currentChar = stack.pop()
        }
        currentChar = stack.pop()
        let multiplier = ""
        while(!Number.isNaN(Number(currentChar))) {
            multiplier = currentChar + multiplier
            currentChar = stack.pop()
        }
        stack.push(currentChar)
        stack.push(innerString.repeat(Number(multiplier)))
    }
    
    return stack.join('')
};