Easy Solution using Recursion | 0ms - Beats 100% | c++
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves parsing a chemical formula and counting the number of atoms 
![Screenshot 2024-07-14 at 3.03.32\u202FPM.png](https://assets.leetcode.com/users/images/43fac0bf-f783-4d37-8d6f-11933d4c81c8_1720949628.2278724.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves parsing a chemical formula and counting the number of atoms for each element. This formula may contain nested parentheses, which complicates the counting process. The goal is to correctly interpret these nested structures and compute the total count for each element.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Initialization and Helper Functions:**\n- In class Solution defined a public integer i to track the current index while parsing.\n- Implement a helper function convertToInteger(string s) to convert a numeric string to an integer, returning 1 for empty strings.\n\n**Recursive Parsing Function (calc):**\n- *calc()* takes a string s representing the chemical formula and returns a map (mp) that stores the count of each element.\nIterate through the string:\n- If an uppercase letter is encountered, it marks the start of an element name. Append subsequent lowercase letters to complete the element name.\n- If digits follow, they represent the count of the element. Use convertToInteger to get this count and update the map.\n- If a \'(\', it indicates the start of a nested formula. Recursively call calc to parse the nested formula.\n- If a \')\', it indicates the end of a nested formula. Parse the subsequent digits to get the multiplier for the nested formula. Multiply the counts in the current map by this multiplier and return the map.\n\n**Main Function (countOfAtoms):**\n- Initialize the index i to 0.\n- Call the calc function to parse the entire string.\n- Construct the final result by iterating through the map and forming the output string.\n\n#\n#  Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Parsing through the string takes $$O(n)$$, where n is the length of the string.\n- Each recursive call processes a portion of the string, and there could be multiple such calls due to nested parentheses. However, since each character is processed exactly once, the overall time complexity remains $$O(n)$$ \n\n\n# Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- The space required for the map to store element counts is $$O(m)$$, where \uD835\uDC5A is the number of unique elements.\n- Additional space is used for recursion stack, which in the worst case (completely nested formulas) could be $$O(n)$$.\nTherefore, the total space complexity is $$O(n+m)$$.\n\n# Code\n\n```\nclass Solution {\npublic:\n    int i;\n\n    int convertToInteger(string s)\n    {\n        if(s == "")\n        {\n            return 1;\n        }\n        return stoi(s);\n    }\n    map<string,int> calc(string s)\n    {\n        int n=s.size(),j;\n        map<string,int> mp;\n        while(i < n)\n        {\n            if(isupper(s[i])) \n            {\n                j = i;\n                string element,cnt;\n                element+=s[j++];\n                while(j < n && islower(s[j]))\n                {\n                    element+=s[j];\n                    j++;\n                }\n                while(j < n && isdigit(s[j]))\n                {\n                    cnt+=s[j];\n                    j++;\n                }\n                i = j;\n                mp[element]+=convertToInteger(cnt);\n            }\n            else if(s[i] == \'(\')\n            {\n                i++;\n                auto temp = calc(s);\n                for(auto p : temp)\n                {\n                    mp[p.first]+=p.second;\n                }\n            }\n            else //if s[i] == \')\'\n            {\n                i++;\n                string cnt;\n                while(i < n && isdigit(s[i]))\n                {\n                    cnt+=s[i];\n                    i++;\n                }\n                if(cnt == "")\n                {\n                    continue;\n                }\n                int count = convertToInteger(cnt);\n                for(auto p : mp)\n                {\n                    mp[p.first]*=count;\n                }\n                return mp;\n            }\n        }\n        return mp;\n    }\n    string countOfAtoms(string s) \n    {\n        i = 0;\n        auto mp = calc(s);\n        string ans;\n        for(auto p : mp)\n        {\n            ans+=p.first;\n            if(p.second == 1)\n            {\n                continue;\n            }\n            ans+=to_string(p.second);\n        }\n        return ans;\n    }\n};\n```\n***Recursion is fun isn\'t it?***\n\n![Screenshot 2024-07-14 at 3.00.05\u202FPM.png](https://assets.leetcode.com/users/images/595c18b2-4149-498f-ac1b-3039ab958dc3_1720949541.7785807.png)\n
['String', 'Recursion', 'C++']