0ms! Beats 100%!! Detailed Step by Step Explanation with Stack
\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires counting the number of each type of atom in a chemical for
![image.png](https://assets.leetcode.com/users/images/047b7fc0-70ba-4faf-ae55-7669546a6800_1720924929.8897164.png)\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires counting the number of each type of atom in a chemical formula and returning a string representation of the counts. The formula may contain nested parentheses that represent groups of atoms, and the count for each group may be specified after the closing parenthesis. If a count is not provided, it defaults to 1.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo solve this problem, we use a stack to handle the nested structure and a map to count the atoms. The stack helps us manage different levels of nested groups in the formula. Here are the main steps in the solution:\n\n1. Initialize a Stack and Iterate through the Formula:\n\n- We use a stack of maps, where each map counts the atoms at a certain level of nesting.\n- We iterate through the formula character by character.\n2. Handle Different Characters:\n\n- \'(\': When encountering an open parenthesis, we push a new empty map onto the stack to start a new group.\n- \')\': When encountering a close parenthesis, we pop the top map from the stack and multiply all its counts by the number following the parenthesis (if any). These counts are then added to the map below it on the stack.\n- Atoms: For atom names (which start with an uppercase letter and may have lowercase letters following), we extract the name and count (if any). The count is defaulted to 1 if not specified. We then update the top map on the stack with this atom and its count.\n3. Construct the Result:\n\n- After processing the entire formula, the top map on the stack contains the final counts of all atoms.\n- We construct the result string by iterating through the sorted keys of the map and appending each atom and its count (if greater than 1) to the result string.\n\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Please upvote if you like the solution.\n\n# Code\n```\nclass Solution {\n    public:\n    string countOfAtoms(string formula) {\n        stack<map<string, int>> stk;\n        stk.push({});\n        int i = 0, n = formula.size();\n\n        while (i < n) {\n            if (formula[i] == \'(\') {\n                stk.push({});\n                i++;\n            } else if (formula[i] == \')\') {\n                auto top = stk.top();\n                stk.pop();\n                i++;\n                int start = i, multiplier = 1;\n                while (i < n && isdigit(formula[i])) i++;\n                if (i > start) multiplier = stoi(formula.substr(start, i - start));\n                for (auto &p : top) {\n                    stk.top()[p.first] += p.second * multiplier;\n                }\n            } else {\n                int start = i;\n                i++;\n                while (i < n && islower(formula[i])) i++;\n                string name = formula.substr(start, i - start);\n                start = i;\n                while (i < n && isdigit(formula[i])) i++;\n                int count = i > start ? stoi(formula.substr(start, i - start)) : 1;\n                stk.top()[name] += count;\n            }\n        }\n\n        string res;\n        for (auto &p : map<string, int>(stk.top())) {\n            res += p.first;\n            if (p.second > 1) res += to_string(p.second);\n        }\n        return res;\n    }\n};\n```
['String', 'Stack', 'C++']