Java || Explained meaning of Stack of Map || Inline details as well
// We need to give a final formula with the element and its num of molucules appended in INCREASING lexicographical order\n// Here is what Stack of Map does:\n/
// We need to give a final formula with the element and its num of molucules appended in INCREASING lexicographical order\n// Here is what Stack of Map does:\n// As soon as the formula sees \'(\' this means that a new SUB formula would be getting created inside and that new formula with different elements and their num of molucules (in sub formula) will be added with the formula which got created before \'(\' so we push the map of formula which we find before \'(\' into the stack\n\n// As soon as we see \')\', this means the SUB Formula we were trying to create is done and hence we should add the freq of elements into previously created formula (if exists) so we pop from the stack\n\n// So here, the centre most formula between "(" & ")" will be addressed first\n\n// TC : O(N) -> length of formula\n// SC : O(M) -> M is the total num of different elements in one formula\n```\nclass Solution {\n    public String countOfAtoms(String formula) {\n        Stack<Map<String, Integer>> mapStack = new Stack<>(); // Map -> Element -> Freq\n        Map<String, Integer> map = new HashMap<>();\n        \n        int i = 0, n = formula.length();\n        while(i < n) {\n            char ch = formula.charAt(i);\n            i++; // as soon as you read the char, increase the index\n            \n            if(ch == \'(\') { // if \'(\' is encountered, push the existing map into stack and initialize new map for SUB formula\n                mapStack.push(map);\n                map = new HashMap<>();\n            } else if (ch == \')\') { // this is where we re-join the SUB formulas\n                int freq = 0;\n                \n                while(i < n && Character.isDigit(formula.charAt(i))) { // find the num of molucules for each elements for SUB formula which is outside ")"\n                    freq = freq * 10 + formula.charAt(i) - \'0\';\n                    i++; // don\'t forget to increment index\n                }\n                \n                if(freq == 0) freq = 1;\n                \n                if(!mapStack.isEmpty()) { // if stack is empty, this means that this is the final SUB formula (without outside formula)\n                    Map<String, Integer> temp = map; // assign present map to new temp map (this contains the element and its count of PRESENT SUB formula)\n                    map = mapStack.pop(); // now map would have previously created formula before the present SUB formula\n\n                    for(String tempKey : temp.keySet()) { // the present SUB formula map keys needs to be multiplied with the frew calc above and added to same element freq before this SUB formula\n                        map.put(tempKey, map.getOrDefault(tempKey, 0) + temp.get(tempKey) * freq);\n                    }\n                }\n            } else {\n                int startIdx = i - 1; // form the Element\n                while(i < n && formula.charAt(i) >= \'a\' && formula.charAt(i) <= \'z\') { // small char means that the name of elem contains these char\n                    i++;\n                }\n                \n                String element = formula.substring(startIdx, i); // startIdx would have a CAPITAL char and rest small char\n                int freq = 0;\n                \n                while(i < n && Character.isDigit(formula.charAt(i))) {\n                    freq = freq*10 + formula.charAt(i) - \'0\';\n                    i++;\n                }\n                \n                if(freq == 0) freq = 1;\n                \n                map.put(element, map.getOrDefault(element, 0) + freq);\n            }\n        }\n        \n        StringBuilder sb = new StringBuilder();\n        List<String> list = new ArrayList<>(map.keySet());\n        Collections.sort(list);\n        for(String ele : list) {\n            sb.append(ele);\n            if(map.get(ele) > 1 ) {\n                sb.append(map.get(ele));\n            }\n        }\n        \n        return sb.toString();\n    }\n}\n```
[]