🔥🔥Beats 100% | Easy Solution with explanation in java,c++,python
Explanation\nThe goal is to count the number of atoms in a chemical formula string, which can include nested structures with parentheses. We use a stack to hand
# Explanation\nThe goal is to count the number of atoms in a chemical formula string, which can include nested structures with parentheses. We use a stack to handle these nested structures efficiently.\n\n# Steps:\n# Initialize a Stack:\n\n- We use a stack to keep track of the counts of atoms at different levels of nesting.\n- Initially, push an empty map onto the stack to represent the top level of the formula.\n# Iterate through the Formula:\n\nWe iterate through each character of the formula.\n\n# Open Parenthesis \'(\':\n\n- When encountering \'(\', push a new empty map onto the stack. This marks a new level of nesting.\n# Close Parenthesis \')\':\n\n- When encountering \')\', pop the top map from the stack. This map contains counts of atoms within the parenthesis.\n- Determine the multiplier following the parenthesis (if any). Multiply all counts in the popped map by this multiplier.\n- Merge these multiplied counts into the map now on the top of the stack.\n# Element:\n\n- Identify the element\'s name (which starts with an uppercase letter and may include lowercase letters).\n- Determine the count following the element name (default is 1 if no number follows).\n- Add this element and its count to the map on the top of the stack.\n# Build the Result:\n\n- After processing the entire formula, pop the final map from the stack. \n- This map now contains the counts of all atoms in the formula.\n- Extract the keys (atom names) from the map and sort them.\nConstruct the result string by appending each atom and its count (if greater than 1) to a StringBuilder.\n\n# Code\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```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                stk.push({});\n                i++;\n            } else if (formula[i] == \')\') {\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                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        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        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![e6f4f26f-a7f5-465b-8ec1-aa665db072f9_1719537871.6475258.png](https://assets.leetcode.com/users/images/df3c5275-7efa-4676-980b-d1c1924fd958_1720926282.22627.png)\n\n
['C++', 'Java', 'Python3']