Beats 100%🤜🏻🤛🏻 || Easy detailed solution with example🫣🫣 || C++ || JAVA || Python ||
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind the solution is to use a stack to manage nested structures in the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind the solution is to use a stack to manage nested structures in the chemical formula, and an unordered_map to count the occurrences of each atom. By leveraging the stack, the solution can correctly handle the hierarchical nature of the formula, including nested parentheses and their multipliers.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Stack for Nested Structures:**\n    - Use a stack to handle nested parentheses. Each level of nesting, indicated by a pair of parentheses, is represented by a new map on the stack.\n    - When encountering an opening parenthesis (, push a new empty map onto the stack to start a new level.\n    - When encountering a closing parenthesis ), pop the top map, multiply its contents by the multiplier that follows the parenthesis, and merge it back into the new top map on the stack.\n\n2. **Map for Atom Counting:**\n    - Each map on the stack keeps track of the count of atoms at the current level of nesting.\n    - When encountering an atom or group of atoms, update the count in the top map on the stack.\n    - After processing the entire formula, the stack will have one map that contains the final counts of all atoms.\n\n3. **Handling Multiplier after Parentheses:**\n    - When a closing parenthesis ) is encountered, the multiplier following it is determined.\n    - Multiply the counts of atoms in the popped map by this multiplier and merge the results back into the previous level.\n\n4. **Final Merging and Sorting:**\n    - Once the formula is fully processed, the remaining map on the stack contains the total counts of all atoms.\n    - Extract the atom counts from this map, sort them alphabetically, and format the counts into the required string format.\n\n# Example Walkthrough\nLet\'s go through the example K4(ON(SO3)2)2 step-by-step:\n\n1. **Initialization:**\n    - Start with an empty map on the stack: stack = [{}]\n\n2. **Processing the Formula:**\n    - K4: Add K with count 4 to the top map.\n       - stack = [{\'K\': 4}]\n    - ( : Push a new empty map to the stack.\n        - stack = [{\'K\': 4}, {}]\n    - O: Add O with count 1 to the new top map.\n        - stack = [{\'K\': 4}, {\'O\': 1}]\n    - N: Add N with count 1 to the new top map.\n       - stack = [{\'K\': 4}, {\'O\': 1, \'N\': 1}]\n    - ( : Push another new empty map to the stack.\n       - stack = [{\'K\': 4}, {\'O\': 1, \'N\': 1}, {}]\n    - S: Add S with count 1 to the new top map.\n        - stack = [{\'K\': 4}, {\'O\': 1, \'N\': 1}, {\'S\': 1}]\n    - O3: Add O with count 3 to the new top map.\n        - stack = [{\'K\': 4}, {\'O\': 1, \'N\': 1}, {\'S\': 1, \'O\': 3}]\n    - )2: Pop the top map, multiply counts by 2, and merge with the map below.\n        - Popped map: {\'S\': 1, \'O\': 3}\n        - Multiplied map: {\'S\': 2, \'O\': 6}\n        - Merged map: {\'O\': 7, \'N\': 1, \'S\': 2}\n        - stack = [{\'K\': 4}, {\'O\': 7, \'N\': 1, \'S\': 2}]\n    - )2: Pop the top map, multiply counts by 2, and merge with the initial map.\n        - Popped map: {\'O\': 7, \'N\': 1, \'S\': 2}\n        - Multiplied map: {\'O\': 14, \'N\': 2, \'S\': 4}\n        - Merged map: {\'K\': 4, \'O\': 14, \'N\': 2, \'S\': 4}\n        - stack = [{\'K\': 4, \'O\': 14, \'N\': 2, \'S\': 4}]\n\n3. **Final Steps:**\n    - Extract the final map: {\'K\': 4, \'O\': 14, \'N\': 2, \'S\': 4}\n    - Sort elements alphabetically and format the output string.\n    - Result: "K4N2O14S4"\n    \n# Complexity\n- **Time complexity:**\n    - Parsing and Processing: O(n), where n is the length of the formula.\n    - Sorting Elements: O(m log m), where m is the number of unique elements.\n    - Overall time complexity is $$O(n + m log m).$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space complexity:**\n    - Stack Storage: O(n) for storing intermediate maps.\n    - Map Storage: O(m) for storing atom counts, where m is the number of unique elements.\n    - Overall space complexity is $$O(n + m).$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n```C++ []\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        stack<unordered_map<string, int>> stk;\n        stk.push({}); // Initialize with an empty map\n        \n        int i = 0, n = formula.length();\n        \n        while (i < n) {\n            if (formula[i] == \'(\') {\n                // Push a new empty map for the new level of nesting\n                stk.push({});\n                i++;\n            } else if (formula[i] == \')\') {\n                // Pop the top map and handle the multiplier\n                unordered_map<string, int> top = stk.top();\n                stk.pop();\n                i++;\n                int start = i;\n                while (i < n && isdigit(formula[i])) {\n                    i++;\n                }\n                int multiplier = start < i ? stoi(formula.substr(start, i - start)) : 1;\n                for (auto& kv : top) {\n                    stk.top()[kv.first] += kv.second * multiplier;\n                }\n            } else {\n                // Handle the element and its count\n                int start = i++;\n                while (i < n && islower(formula[i])) {\n                    i++;\n                }\n                string element = formula.substr(start, i - start);\n                start = i;\n                while (i < n && isdigit(formula[i])) {\n                    i++;\n                }\n                int count = start < i ? stoi(formula.substr(start, i - start)) : 1;\n                stk.top()[element] += count;\n            }\n        }\n        \n        // Prepare the result map\n        unordered_map<string, int> result = stk.top();\n        vector<string> elements;\n        for (auto& kv : result) {\n            elements.push_back(kv.first);\n        }\n        sort(elements.begin(), elements.end());\n        \n        // Build the result string\n        string res;\n        for (const auto& element : elements) {\n            res += element;\n            if (result[element] > 1) {\n                res += to_string(result[element]);\n            }\n        }\n        \n        return res;\n    }\n};\n\n```\n```java []\nclass Solution {\n      public String countOfAtoms(String formula) {\n        Stack<Map<String, Integer>> stack = new Stack<>();\n        stack.push(new HashMap<>());\n        int len = formula.length();\n\n        for (int i = 0; i < len; ) {\n            if (formula.charAt(i) == \'(\') {\n                stack.push(new HashMap<>());\n                i++;\n            } else if (formula.charAt(i) == \')\') {\n                Map<String, Integer> top = stack.pop();\n                i++;\n                int start = i;\n                while (i < len && Character.isDigit(formula.charAt(i))) i++;\n                int multiplier = start < i ? Integer.parseInt(formula.substring(start, i)) : 1;\n                for (String key : top.keySet()) {\n                    stack.peek().put(key, stack.peek().getOrDefault(key, 0) + top.get(key) * multiplier);\n                }\n            } else {\n                int start = i;\n                i++;\n                while (i < len && Character.isLowerCase(formula.charAt(i))) i++;\n                String element = formula.substring(start, i);\n                start = i;\n                while (i < len && Character.isDigit(formula.charAt(i))) i++;\n                int count = start < i ? Integer.parseInt(formula.substring(start, i)) : 1;\n                stack.peek().put(element, stack.peek().getOrDefault(element, 0) + count);\n            }\n        }\n\n        Map<String, Integer> result = stack.pop();\n        List<String> elements = new ArrayList<>(result.keySet());\n        Collections.sort(elements);\n        StringBuilder sb = new StringBuilder();\n        for (String element : elements) {\n            sb.append(element);\n            int count = result.get(element);\n            if (count > 1) sb.append(count);\n        }\n        return sb.toString();\n    }\n}\n```\n```python []\nclass Solution:\n    def countOfAtoms(self, formula: str) -> str:\n        stack = [{}]\n        i, n = 0, len(formula)\n\n        while i < n:\n            if formula[i] == \'(\':\n                stack.append({})\n                i += 1\n            elif formula[i] == \')\':\n                top = stack.pop()\n                i += 1\n                i_start = i\n                while i < n and formula[i].isdigit():\n                    i += 1\n                multiplier = int(formula[i_start:i] or 1)\n                for element, count in top.items():\n                    stack[-1][element] = stack[-1].get(element, 0) + count * multiplier\n            else:\n                i_start = i\n                i += 1\n                while i < n and formula[i].islower():\n                    i += 1\n                element = formula[i_start:i]\n                i_start = i\n                while i < n and formula[i].isdigit():\n                    i += 1\n                count = int(formula[i_start:i] or 1)\n                stack[-1][element] = stack[-1].get(element, 0) + count\n\n        result = stack.pop()\n        sorted_elements = sorted(result.keys())\n        return \'\'.join(f"{element}{(result[element] if result[element] > 1 else \'\')}" for element in sorted_elements)\n```\n![Screenshot.png](https://assets.leetcode.com/users/images/97c0916a-a2df-4c7b-aa87-6ab807e311d5_1720931015.5213592.png)\n\n
['Hash Table', 'String', 'Stack', 'Sorting', 'Python', 'C++', 'Java']