Simple Explanation ✨
Intuition\nTo count the number of atoms in a given chemical formula, we need to correctly parse nested structures (parentheses) and multiply counts by appropria
# Intuition\nTo count the number of atoms in a given chemical formula, we need to correctly parse nested structures (parentheses) and multiply counts by appropriate multipliers.\n\n# Approach\n1. **Stack Initialization**\nWe use a stack to handle nested parentheses and keep track of atom counts in different scopes. This stack will help us manage the transitions between different levels of nested structures in the formula.\n\n2. **Iteration**\nWe iterate through each character in the formula string. During this iteration, we handle three main cases:\n\n- 1. **Opening Parenthesis \'(\':**\n\n  - When we encounter an opening parenthesis (, it signifies the start of a new nested scope.\n  - We push the current state (currMap, which keeps track of the atom counts in the current scope) onto the stack.\n  - We then reset currMap to an empty map to start a new scope.\n\n- 2. **Closing Parenthesis \')\':**\nWhen we encounter a closing parenthesis ), it signifies the end of the current nested scope.\n  - We pop the previous state (topMap) from the stack.\n  - We then determine the multiplier by reading the digits immediately following the ). This multiplier is applied to all atoms within the current scope.\n  - We merge the counts from the current scope (multiplied by the multiplier) back into the previous scope (topMap).\n\n- 3. **Element Detection:**\n  - When we encounter an uppercase letter, it indicates the start of an element.\n  - We identify the full element name by checking for any subsequent lowercase letters.\n  - After identifying the element name, we look for any digits that follow the element name to determine its count.\n  - If no digits are found, the count is considered to be 1.\nWe then update the count of this element in the currMap.\n\n3. **Merge Counts**\n- After the iteration, we merge any remaining counts from nested scopes back into the main scope. This is handled by popping the stack and updating the counts in the main scope.\n\n4. **Sort and Format**\nOnce we have the final counts for all atoms, we:\n\n- Sort the elements by their names.\nFormat the output string by appending each element name followed by its count (if the count is greater than 1).\n\n5. **Example Walkthrough**\nConsider the example formula "K4(ON(SO3)2)2":\n\nInitial parsing identifies "K4" with currMap = {K=4}.\nEncountering (, we push the current map onto the stack.\nParsing "ON" within the parentheses with currMap = {O=1, N=1}.\nEncountering ( again, we push the current map onto the stack.\nParsing "SO3" within the innermost parentheses with currMap = {S=1, O=3}.\nEncountering )2, we pop and merge counts with a multiplier of 2 resulting in currMap = {S=2, O=6}.\nEncountering )2 again, we pop and merge counts with a multiplier of 2 resulting in currMap = {K=4, O=14, N=2, S=4}.\nFinal sorting and formatting give us "K4N2O14S4".\n\n# Complexity\n- Time complexity: $$O(n)$$ where n is the length of the formula string. Each character is processed once.\n- Space complexity: $$O(n)$$ due to the stack and hash maps used to store the counts.\n\n# Code\n```\nclass Solution {\n    public String countOfAtoms(String formula) {\n        int n = formula.length();\n        HashMap<String, Integer> currMap = new HashMap<>();\n        Deque<HashMap<String, Integer>> st = new ArrayDeque<>();\n        int i =0;\n        while(i<n){\n            if(formula.charAt(i)==\'(\'){\n                // Push the current map to stack and start a new one\n                st.push(currMap);\n                currMap = new HashMap<>();\n                i++;\n            }\n            else if(formula.charAt(i)==\')\'){\n                int iStart = ++i;\n                int mul = 0;\n                while(i<n && Character.isDigit(formula.charAt(i))){\n                    mul = mul*10 + formula.charAt(i) - \'0\';\n                    i++;\n                }\n                if(mul==0) mul=1;\n                // Pop the stack and merge the counts\n                HashMap<String, Integer> topMap = currMap;\n                currMap = st.pop();\n                for(String key: topMap.keySet()){\n                    currMap.put(key, currMap.getOrDefault(key, 0) +  topMap.get(key)* mul);\n                }\n            }\n            else{\n                // Parse the atom name\n                int iStart = i++;\n                while(i<n && Character.isLowerCase(formula.charAt(i))){\n                    i++;\n                }\n                String name = formula.substring(iStart, i);\n                //parse the count\n                iStart = i;\n                int count =0;\n                while(i<n && Character.isDigit(formula.charAt(i))){\n                    count = count*10 + formula.charAt(i) - \'0\';\n                    i++;\n                }\n                if(count==0)count=1;\n                currMap.put(name, currMap.getOrDefault(name, 0)+count);\n            }\n        }\n        //format the result\n        StringBuilder ans = new StringBuilder();\n        List<String> keys = new ArrayList<>(currMap.keySet());\n        Collections.sort(keys);\n        for(String key : keys){\n            ans.append(key);\n            if(currMap.get(key)>1){\n                ans.append(currMap.get(key));\n            }\n        }\n        return ans.toString();\n    }\n}\n```
['Java']