Java Recursion + Map
\nWe used TreeMap here so that we could have entries sorted by String[Formula] in the end.\n\n if(capital_letter) -> \n               1. put prevFormula and its
\nWe used TreeMap here so that we could have entries sorted by String[Formula] in the end.\n\n if(capital_letter) -> \n*               1. put prevFormula and its count in the map\n                2. prevFormula=capital_letter & reset the count\n                \nif(small_letter) -> \n*             1. append to pre-computed formula\n                \nif(\'(\') -> \n* \t\t\t\t1. put prevFormula and its count in the map & reset prevFormula & count \n\t\t\t\t2. make recursive call \n\t\t\t\t3. add returned map result to current map\n       \nif(\')\') -> \n* \t\t\t\t1. put prevFormula and its count in the map & reset those \n\t\t\t\t2. Compute count next to \')\'  \n\t\t\t\t3. Multiply the count in the map\n\t\t\t\t4. return the map \n\n\n```\nclass Solution {\n    int i=0;\n    \n    public String countOfAtoms(String formula) {\n        if(formula == null || formula.isEmpty())\n            return "";\n        \n        TreeMap<String,Integer> map = countOfAtomsHelper(formula);\n\n        StringBuilder sb = new StringBuilder();\n        for(Map.Entry<String,Integer> e : map.entrySet())\n            sb.append(e.getKey() + (e.getValue()==1 ? "" : e.getValue()) ) ;\n        \n        return sb.toString();\n    }\n    \npublic TreeMap<String,Integer> countOfAtomsHelper(String formula) {\n        \n        TreeMap<String,Integer> map = new TreeMap<>();\n        String prev = "";\n        int num = 0; \n        \n        while(i<formula.length()){\n            \n            char ch = formula.charAt(i);\n            \n            if(isBigChar(ch)){\n                putPrev(map, prev, num);\n                prev = ""+ch;\n                num = 0;\n            } \n            else if(Character.isDigit(ch)){\n               num = num*10 + ch -\'0\'; \n            } \n            else if(Character.isLowerCase(ch)){\n                prev = prev + ch;      \n            }\n            else if(ch==\'(\'){\n                putPrev(map, prev, num);        \n                prev = ""; num = 0;             \n                \n                i++;\n                \n                TreeMap<String,Integer> subMap = countOfAtomsHelper(formula);\n                // add this subMap to main Map \n                for(Map.Entry<String,Integer> e : subMap.entrySet()){\n                    map.put(e.getKey(), map.getOrDefault(e.getKey(), 0) + e.getValue());\n                }\n                \n                i--; // when we returned from ) i is already pointing to next element  \n            } \n            else { // ch==\')\'\n                putPrev(map, prev, num);       \n                prev = ""; num = 0;            \n                \n                i++;\n                \n                // there could be a number then compute that number \n                int count=0;\n                while(i<formula.length() && Character.isDigit(formula.charAt(i))){\n                    count = count*10 + formula.charAt(i) - \'0\';\n                    i++;\n                }\n                \n                count = count==0 ? 1 : count; \n                if(count!=1){\n                    for(Map.Entry<String,Integer> e : map.entrySet()){\n                        map.put(e.getKey(), e.getValue()*count);\n                    }\n                }\n                \n                return map;\n            }\n            \n            i++;\n        }\n        \n        putPrev(map, prev, num); // dont forget the last computed formula \n        \n        return map;\n    }\n    \n    boolean isBigChar(char ch){\n        if(ch>=\'A\' && ch<=\'Z\')\n            return true;\n        return false; \n    }\n     \n    void putPrev(Map<String,Integer> map, String prev, int num){\n        if(prev.isEmpty())\n            return;\n        num = num==0 ? 1 : num;\n        map.put(prev, map.getOrDefault(prev,0) + num);\n    }\n}\n```
['Recursion', 'Java']