[Java] 2ms, faster than 100.00%, with explanation, O(N)time
O(N)time O(N)space. \nRuntime: 2 ms, faster than 100.00% of Java online submissions for Number of Atoms.\nMemory Usage: 37.4 MB, less than 100.00% of Java onlin
**O(N)time O(N)space.** \n**Runtime: 2 ms, faster than 100.00% of Java online submissions for Number of Atoms.\nMemory Usage: 37.4 MB, less than 100.00% of Java online submissions for Number of Atoms.** \n```\nclass Solution {\n    public String countOfAtoms(String formula) {\n        //record (\'s index in element count,   CaHO( :   index is 3\n        LinkedList<Integer> recordFrontBracket = new LinkedList<>();\n        \n        int len = formula.length();\n        //record the element name,  CaHO   Ca \u2192 H \u2192 O\n        ArrayList<String> atoms = new ArrayList<>(len);\n        //record count of element in atoms,  CaHO 1 \u2192 1 \u2192 1\n        ArrayList<Integer> counts = new ArrayList<>(len);\n        for (int i = 0; i < len; i++) {\n            char c = formula.charAt(i);\n            if (c == \'(\') {\n                //record (\'s index\n                recordFrontBracket.add(atoms.size());\n            } else if (c == \')\') {\n                //get the number after `()`\n                int number = 0;\n                while (i + 1 < len && isDigital(formula.charAt(i + 1))) {\n                    number = number * 10 + formula.charAt(i + 1) - \'0\';\n                    i++;\n                }\n                if (number == 0) {\n                    //default as 1\n                    number = 1;\n                }\n                //get the match \'(\' with \')\'\n                int index = recordFrontBracket.removeLast();\n                \n                //multiply number from count[index] to count[end]\n                //Ca(HO)2  \n                //atoms is [Ca, H, O],   count is [1,1,1]\n                //index = 1, end is 2,   count \u2192  [1,2,2]\n                for (int j = index; j < counts.size(); j++) {\n                    counts.set(j, counts.get(j) * number);\n                }\n            } else if (isUpperCase(c)) {\n                //get the element name\n                int t = i;\n                while (t + 1 < len && isLowerCase(formula.charAt(t + 1))) {\n                    t++;\n                }\n                //add to atoms list\n                atoms.add(formula.substring(i, t + 1));\n                i = t;                \n                //get the number after elment\n                int count = 0;\n                while (i + 1 < len && isDigital(formula.charAt(i + 1))) {\n                    count = count * 10 + formula.charAt(i + 1) - \'0\';\n                    i++;\n                }\n                if (count == 0) {\n                    //default as 1\n                    count = 1;\n                }\n                //add to count list\n                counts.add(count);\n            }\n        }\n        //get the element name and count\n        Map<String, Integer> map = new HashMap<>();\n        for (int i = 0; i < atoms.size(); i++) {\n            map.put(atoms.get(i), map.getOrDefault(atoms.get(i), 0) + counts.get(i));\n        }\n        //put the elemant name in arr\n        String[] arr = new String[map.size()];\n        Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();\n        int index = 0;\n        while (iterator.hasNext()) {\n            arr[index] = iterator.next().getKey();\n            index++;\n        }\n        //sort element name\n        Arrays.sort(arr);\n        StringBuilder res = new StringBuilder();\n        for (int i = 0; i < arr.length; i++) {\n            //append element name\n            res.append(arr[i]);\n            //if element count is not 1, append the count\n            int count = map.get(arr[i]);\n            res.append(count != 1 ? count : "");\n        }\n        return res.toString();\n    }\n\n    public boolean isDigital(char c){\n        return c >= \'0\' && c <= \'9\';\n    }\n\n    public boolean isUpperCase(char c){\n        return c >= \'A\' && c <= \'Z\';\n    }\n\n    public boolean isLowerCase(char c) {\n        return c >= \'a\' && c <= \'z\';\n    }\n}\n```
[]