Simple and easy to understand ✅|| Beats 100% runtime users ✅|| stack and map implementation || cpp
Intuition\n Describe your first thoughts on how to solve this problem. \nThe optimized solution maintains the original logic but reduces memory usage by efficie
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n*The optimized solution maintains the original logic but reduces memory usage by efficiently handling nested parentheses and merging element counts directly into the top map on the stack. This avoids unnecessary map copying and excessive memory allocation. The core idea is to streamline the parsing and merging process while keeping the operations straightforward and consistent with the initial logic, ensuring that we stay within memory limits while accurately counting atom occurrences.*\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Initialization: Use a stack to manage nested scopes of atom counts. Start by pushing an empty map onto the stack to store the counts of atoms.\n\n- Parsing the Formula: Traverse the input formula character by character using an index:\n\n- Opening Parenthesis (\'(\'): Push a new empty map onto the stack to start a new scope.\n- Closing Parenthesis (\')\'): Pop the top map from the stack, indicating the end of the current scope. Calculate the multiplier for this scope by reading any subsequent digits. Multiply all atom counts in this map by the multiplier and merge these counts into the map below it on the stack.\n- Atoms and Counts: When encountering an atom, collect its full name (considering uppercase followed by lowercase letters) and any digits representing its count. If no digits follow the atom, the count defaults to 1. Update the count of this atom in the top map on the stack.\n- Final Aggregation: After parsing the entire formula, the stack\'s top map contains the aggregated counts of all atoms. Transfer these counts into a sorted map to ensure the atoms are listed in lexicographical order.\n\n- Result Construction: Construct the final result string by concatenating each atom and its count (omitting the count if it is 1).\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTC : **O(N)**\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSC : **O(N)**\n# Code\n```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        stack<unordered_map<string, int>> st;\n        st.push(unordered_map<string, int>());\n\n        int index = 0;\n        while (index < formula.length()) {\n            if (formula[index] == \'(\') {\n                st.push(unordered_map<string, int>());\n                index++;\n            } else if (formula[index] == \')\') {\n                unordered_map<string, int> currMap = st.top();\n                st.pop();\n                index++;\n                string multiplier;\n                while (index < formula.length() && isdigit(formula[index])) {\n                    multiplier += formula[index];\n                    index++;\n                }\n                int mult = multiplier.empty() ? 1 : stoi(multiplier);\n                for (auto& [atom, count] : currMap) {\n                    st.top()[atom] += count * mult;\n                }\n            } else {\n                string currAtom;\n                currAtom += formula[index++];\n                while (index < formula.length() && islower(formula[index])) {\n                    currAtom += formula[index++];\n                }\n                string currCount;\n                while (index < formula.length() && isdigit(formula[index])) {\n                    currCount += formula[index++];\n                }\n                int count = currCount.empty() ? 1 : stoi(currCount);\n                st.top()[currAtom] += count;\n            }\n        }\n\n        map<string, int> finalMap(st.top().begin(), st.top().end());\n        string ans;\n        for (const auto& [atom, count] : finalMap) {\n            ans += atom;\n            if (count > 1) {\n                ans += to_string(count);\n            }\n        }\n        return ans;      \n    }\n};\n```\n![upvote_pic.webp](https://assets.leetcode.com/users/images/5a73420b-1a9f-4a14-bc26-8507a4e78bb0_1720947040.3774624.webp)\n\n\n
['C++']