Number of Atoms.java

class Solution {
    public String countOfAtoms(String formula) {
        Map<String, Integer> map = new HashMap<>();
        int[] stack = new int[1000];
        int top = 0, multiplier = 1, freq = 0;
        char[] c = formula.toCharArray();
        for(int i = c.length - 1; i >= 0; i--) {
            if(c[i] >= 'a' && c[i] <= 'z') {
                int end = i--;
                while(i >= 0 && c[i] >= 'a' && c[i] <= 'z') i--;
                String key = new String(c, i, end - i + 1);
                map.put(key, map.getOrDefault(key, 0) + Math.max(freq, 1) * multiplier);
                freq = 0;
            } else if(c[i] >= 'A' && c[i] <= 'Z') {
                String key = new String(c, i, 1);
                map.put(key, map.getOrDefault(key, 0) + Math.max(freq, 1) * multiplier);
                freq = 0;
            } else if(c[i] >= '0' && c[i] <= '9') {
                freq = c[i] - '0';
                int p = 10;
                while(i-1 >= 0 && c[i-1] >= '0' && c[i-1] <= '9') {
                    freq += p * (c[--i] - '0');
                    p *= 10;
                }
            } else if(c[i] == ')') {
                stack[top++] = multiplier;
                multiplier *= Math.max(freq, 1);
                freq = 0;
            } else {
                multiplier = stack[--top];
            }
        }
        List<String> keys = new ArrayList<>(map.keySet());
        Collections.sort(keys);
        StringBuilder sb = new StringBuilder();
        for(String key: keys) {
            sb.append(key);
            int f = map.get(key);
            if(f > 1) sb.append(f);
        }
        return sb.toString();
    }
}