Category: Coding Prep

string decodedString(string &s) {
        // code here
        stack<char> st;
        string ans;
        for(int i=0;i<s.size(); i++) {
            if(s[i] != ']') st.push(s[i]);
            else {
                string temp;
                while(!st.empty() && st.top() != '[') {
                    temp.push_back(st.top());
                    st.pop();
                }
                reverse(temp.begin(), temp.end());
                st.pop();
                string dig;
                while(!st.empty() && isdigit(st.top())) {
                    dig.push_back(st.top());
                    st.pop();
                }
                reverse(dig.begin(), dig.end());
                string word;
                for(int j=0; j<stoi(dig); j++) {
                    word.append(temp);
                }
                for(char c:word) 
                    st.push(c);
            }
        }
        while(!st.empty()) {
            ans.push_back(st.top());
            st.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans; 
    }

vector<int> calculateSpan(vector<int>& arr) {
        // write code here
        stack<int> st;
        vector<int> ans(arr.size());
        for(int i=0; i<arr.size(); i++) {
            while(!st.empty() && arr[st.top()] <= arr[i])
                st.pop();
            if(st.empty()) 
                ans[i] = i+1;
            else
                ans[i] = i-st.top();
            st.push(i);
        }
        return ans;
    }

vector<int> nextLargerElement(vector<int>& arr) {
        // code here
        int n = arr.size();
        vector<int> ans(n, -1);
        stack<int> st;
        for(int i=n-1; i>=0; i--) {
            while(!st.empty() && arr[i] >= st.top()) st.pop();
            if(!st.empty()) ans[i] = st.top();
            st.push(arr[i]);
        }
        return ans;
     }

int maxLength(string& s) {
        // code here
        int maxlen = 0;
        stack<int> st;
        st.push(-1);
        for(int i=0; i<s.size(); i++) {
            if(s[i] == '(') st.push(i);
            else {
                st.pop();
                if(!st.empty()) maxlen = max(maxlen, i-st.top());
                else st.push(i);
            }
        }
        return maxlen;
    }