DecodeString.java

package stack;

import java.util.Stack;
/**
 * Created by gouthamvidyapradhan on 12/04/2018.
 * Given an encoded string, return it's decoded string.
 * <p>
 * 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.
 * <p>
 * You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
 * <p>
 * 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 like 3a or 2[4].
 * <p>
 * Examples:
 * <p>
 * s = "3[a]2[bc]", return "aaabcbc".
 * s = "3[a2[c]]", return "accaccacc".
 * s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
 *
 * Solution: Maintain a stack and push items when a character other than ] is encountered. When a character ] is
 * encountered pop elements, build string and duplicate it.
 */
public class DecodeString {

    /**
     * Main method
     *
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        System.out.println(new DecodeString().decodeString("100[leetcode]"));
    }

    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ']') {
                StringBuilder stackBuff = new StringBuilder();
                while (stack.peek() != '[') {
                    stackBuff.append(stack.pop());
                }
                stack.pop(); //pop '['
                String num = "";
                while (!stack.isEmpty() && !Character.isAlphabetic(stack.peek()) && stack.peek() != '[') {
                    num = stack.pop() + num;
                }
                String str = stackBuff.reverse().toString();
                StringBuilder stringMultiple = new StringBuilder();
                int N = Integer.parseInt(num);
                while (N-- > 0) {
                    stringMultiple.append(str);
                }
                for (int j = 0; j < stringMultiple.length(); j++) {
                    stack.push(stringMultiple.charAt(j));
                }
            } else stack.push(s.charAt(i));
        }
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        return result.reverse().toString();
    }

}