Decode String Leetcode Solution

Problem Statement

The Decode String LeetCode Solution – “Decode String” asks you to convert the encoded string into a decoded string.

The encoding rule is k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times where k is a positive integer.

Example:

Input:  s = "3[a]2[bc]"

Output: "aaabcbc"

Explanation:

• [a] is repeated 3 times while [bc] is repeated 2 times.
• “aaabcbc” is the decoded string.

Input:  s = "2[abc]3[cd]ef"

Output: "abcabccdcdcdef"

Explanation:

• [abc] is repeated 2 times while [cd] is repeated 3 times and [ef] is repeated 1 time.
• “abcabccdcdcdef” is the decoded string.

Approach

Idea:

1. The main idea to solve this problem is to use Stack.
2. We’ll use a stack of strings to store characters of the string except for opening and closing square brackets.
3. There exist 2 cases:
   1. When a current character is a closing square bracket: pick up all the strings till we get the opening bracket. Again, extract strings till we get some digit which will denote the value of k here. Finally, we need to multiply the string obtained here with k and push it to the stack again.
   2. When the current character is not a closing square bracket: push the string representation of the character to the stack.
4. Finally, extract all strings from the stack, one by one from the top, and append them to the answer string.
5. Note that we need to take care of the positions of characters while appending it to the answer.
6. In the below code, all strings are first reversed while taking from the stack and appended to the answer string and finally the answer string is reversed to get the desired result.

Code

Decode String Leetcode C++ Solution:

class Solution {
public: 
    string decodeString(string s) {
        stack<string> st;
        for(auto& c:s){
            if(c==']'){
                string temp = "",curr = "";
                while(!st.empty() and st.top()!="["){
                    reverse(st.top().begin(),st.top().end());
                    temp += st.top();
                    st.pop();
                }
                
                st.pop();
                string times = "";
                
                while(!st.empty() and st.top()>="0" and st.top()<="9"){
                    times += st.top();
                    st.pop();
                }
                
                reverse(times.begin(),times.end());
                reverse(temp.begin(),temp.end());
                
                int k = stoi(times);
                
                while(k--){
                    curr += temp;
                }
                
                if(!st.empty() and st.top()!="[")
                    st.top() += curr;  
                else
                    st.push(curr);
            }
            else{
                string curr = "";
                curr.push_back(c);
                st.push(curr);
            }
        }
        
        string ans = "";
        while(!st.empty()){
            reverse(st.top().begin(),st.top().end());
            ans += st.top();
            st.pop();
        }
        
        reverse(ans.begin(),ans.end());
        
        return ans;
    }
};

Decode String Leetcode Java Solution:

public class Solution {
    public String decodeString(String s) {
        String res = "";
        Stack<Integer> countStack = new Stack<>();
        Stack<String> resStack = new Stack<>();
        int idx = 0;
        while (idx < s.length()) {
            if (Character.isDigit(s.charAt(idx))) {
                int count = 0;
                while (Character.isDigit(s.charAt(idx))) {
                    count = 10 * count + (s.charAt(idx) - '0');
                    idx++;
                }
                countStack.push(count);
            }
            else if (s.charAt(idx) == '[') {
                resStack.push(res);
                res = "";
                idx++;
            }
            else if (s.charAt(idx) == ']') {
                StringBuilder temp = new StringBuilder (resStack.pop());
                int repeatTimes = countStack.pop();
                for (int i = 0; i < repeatTimes; i++) {
                    temp.append(res);
                }
                res = temp.toString();
                idx++;
            }
            else {
                res += s.charAt(idx++);
            }
        }
        return res;
    }
}

Complexity Analysis for Decode String Leetcode Solution

Time Complexity

The time complexity of the above code is O(N) since we’re iterating for each character, where N = length of the input string.

Space Complexity

The space complexity of the above code is O(N) since we are using a stack to store the string representation of every character.