Given an encoded string, return it's decoded string.

The encoding rule is:k[encoded_string], where theencoded_stringinside the square brackets is being repeated exactlyktimes. Note thatkis guaranteed to be a positive integer.

You may assume that the input string is always valid; 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 won't be input like3aor2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

class Solution {
    public String decodeString(String s) {
        String ans = "";
        Stack<Integer> countStack = new Stack<>();
        Stack<String> ansStack = new Stack<>();

        for (int i = 0; i < s.length(); i++){

            char c = s.charAt(i);

            if (Character.isDigit(c)){
                int sum = c - '0';
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))){
                    sum = sum * 10 + (s.charAt(i + 1) - '0');
                    i++;
                }
                countStack.push(sum);
            }
            else if (c == '['){
                ansStack.push(ans);
                ans = "";
            }
            else if (c == ']'){
                StringBuilder sb = new StringBuilder(ansStack.pop());
                int repeat = countStack.pop();
                for (int k = 0; k < repeat; k++){
                    sb.append(ans);
                }
                ans = sb.toString();
            }
            else{
                ans += c;
            }
        }


        return ans;
    }
}