Beats 100% Results
\n# Approach\n1. Stack Usage: \nI used a stack to manage nested parentheses. Each level of parentheses had its own map to keep track of the atom counts. This wa
\n# Approach\n1. Stack Usage: \nI used a stack to manage nested parentheses. Each level of parentheses had its own map to keep track of the atom counts. This way, every time I encountered a \'(\', I pushed a new map onto the stack. When I encountered a \')\', I popped the top map, applied the multiplicative factor (if any), and then merged this map with the one just below it in the stack.\n2. Parsing the Formula: \nI iterated through each character of the formula. Here\'s how I handled different characters:\n\'(\': I pushed a new empty map onto the stack.\n\')\': I popped the top map, found the multiplicative factor right after the closing parenthesis (if any), multiplied the counts in the popped map by this factor, and merged the results back into the map below it.\n3. Atoms and Numbers: Whenever I encountered an atom (which starts with an uppercase letter and may be followed by lowercase letters), I parsed the name. I then checked for a number that follows the atom name to determine its count. This count was then added to the current map on the stack.\n4. Result:\nAfter processing the entire formula, the top map on the stack contained the final counts of all atoms. I sorted these atoms by name to ensure the result was in the correct order. Finally, I constructed the result string by appending each atom and its count (if greater than 1).\n\n# Complexity\n- Time complexity:\n$$O(n + klog k)$$ \n\n- Space complexity:\n$$O(n+k)$$\n\n# Code\n```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        stack<map<string, int>> stk;\n        stk.push({});\n        int n = formula.size();\n        for (int i = 0; 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;\n                while (i < n && isdigit(formula[i])) i++;\n                int multiplicity = (i > start) ? stoi(formula.substr(start, i - start)) : 1;\n                for (auto &p : top) {\n                    stk.top()[p.first] += p.second * multiplicity;\n                }\n            } else {\n                int start = 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 multiplicity = (i > start) ? stoi(formula.substr(start, i - start)) : 1;\n                stk.top()[name] += multiplicity;\n            }\n        }\n        map<string, int> &count = stk.top();\n        string result;\n        for (auto &p : count) {\n            result += p.first;\n            if (p.second > 1) result += to_string(p.second);\n        }\n        return result;\n    }\n};\n```
['Hash Table', 'String', 'Stack', 'C++']