[Java] O(n + n log n) Parse right to left and maintain multiplier using stack. Beats 100%
Parse string right to left. This has the advantage that we know the current multiplier in case of nested parentheses so that we can directly increment an elemen
Parse string right to left. This has the advantage that we know the current multiplier in case of nested parentheses so that we can directly increment an element\'s count instead of re-visiting it later once matching parenthesis is found. To be able to go back to previous value of multiplier, we use a stack.\n\nFor example: string = ```A(B(C)2D)3E```\nAt E: multiplier = 1 (default value)\nAt D: multiplier = 3 * 1 = 3 (push old value 1 to stack)\nAt C: multiplier = 2 * 3 = 6 (push old value 3 to stack)\nAt B: multiplier = back to 3 (pop from stack)\nAt A: multiplier = back to 1 (pop from stack)\n\nWe maintain element names and their counts in a HashMap so the core problem gets solved in O(n) time. Sorting names requires an additional O(n log n) time.\n\n```\n// 1 ms. 100%\nclass Solution {\n    public String countOfAtoms(String formula) {\n        Map<String, Integer> map = new HashMap<>();\n        int[] stack = new int[1000];\n        int top = 0, multiplier = 1, freq = 0;\n        char[] c = formula.toCharArray();\n        for(int i = c.length - 1; i >= 0; i--) {\n            if(c[i] >= \'a\' && c[i] <= \'z\') {\n                int end = i--;\n                while(i >= 0 && c[i] >= \'a\' && c[i] <= \'z\') i--;\n                String key = new String(c, i, end - i + 1);\n                map.put(key, map.getOrDefault(key, 0) + Math.max(freq, 1) * multiplier);\n                freq = 0;\n            } else if(c[i] >= \'A\' && c[i] <= \'Z\') {\n                String key = new String(c, i, 1);\n                map.put(key, map.getOrDefault(key, 0) + Math.max(freq, 1) * multiplier);\n                freq = 0;\n            } else if(c[i] >= \'0\' && c[i] <= \'9\') {\n                freq = c[i] - \'0\';\n                int p = 10;\n                while(i-1 >= 0 && c[i-1] >= \'0\' && c[i-1] <= \'9\') {\n                    freq += p * (c[--i] - \'0\');\n                    p *= 10;\n                }\n            } else if(c[i] == \')\') {\n                stack[top++] = multiplier;\n                multiplier *= Math.max(freq, 1);\n                freq = 0;\n            } else {\n                multiplier = stack[--top];\n            }\n        }\n        List<String> keys = new ArrayList<>(map.keySet());\n        Collections.sort(keys);\n        StringBuilder sb = new StringBuilder();\n        for(String key: keys) {\n            sb.append(key);\n            int f = map.get(key);\n            if(f > 1) sb.append(f);\n        }\n        return sb.toString();\n    }\n}\n```\n\nSimilar problem to try: [394. Decode String](https://leetcode.com/problems/decode-string/)
['Stack', 'Java']