0 ms|| Easy Beginner Friendly and recursive solution|| Detailed Explanation|| Beats 100%
\n\n# Approach\n Describe your approach to solving the problem. \nThe Approach is quite easy but follow carefully.In the given formula we can have uppercase let
![image.png](https://assets.leetcode.com/users/images/914b7998-83ea-495a-8284-e3a1a8b37b97_1720937925.2051487.png)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe Approach is quite easy but follow carefully.In the given formula we can have uppercase letters, lower case letters, digits and brackets. You have no issues when you encounter a letters or digits. So maintain a hashtable to store these elements and its count. But when you encounter a "("  you have to do the same again. So fo this call the function recursively and maintain a local map for storing the local elements count and when you encounter a ")" search for some digits to count the rest of the atoms if present. then multiply the count with the local map and update the map of the previous recusrion map using this map elements. and return the i value to continue the next parsing.\n# Complexity\n- Time complexity: $$O(n\u22C5klogk)$$, which is effectively $$\uD835\uDC42(\uD835\uDC5B)$$ in most practical cases.\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)$$ -->\nwhere k is number of unique elements present in the formula.\n#        **Please Upvote if you like\uD83E\uDD7A\uD83E\uDD7A and comment if you have any doubts**\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    // Helper function to recursively solve the chemical formula\n    int solve(int i, string s, int n, map<string, int>& prev_map) {\n        map<string, int> t;\n        \n        // Iterate through the formula string\n        for (; i < n; i++) {\n            if (s[i] == \'(\') {\n                // If an opening parenthesis is found, solve the nested formula\n                i = solve(i + 1, s, n, t);\n            } else if (isupper(s[i])) {\n                // If an uppercase letter is found, it indicates the start of an element\n                string temp;\n                temp += s[i];\n                i++;\n                \n                // Check for a lowercase letter indicating the full element symbol\n                if (i < n && islower(s[i])) {\n                    temp += s[i];\n                    i++;\n                }\n                \n                // Parse the element count if it exists\n                int count = 0, j;\n                for (j = i; j < n; j++) {\n                    if (isdigit(s[j])) {\n                        count = count * 10 + (s[j] - \'0\');\n                    } else {\n                        break;\n                    }\n                }\n                \n                // Update the element count in the current map\n                t[temp] += (count == 0) ? 1 : count;\n                i = (count == 0) ? i - 1 : j - 1;\n            } else if (s[i] == \')\') {\n                // If a closing parenthesis is found, process the nested formula\n                i++;\n                int count = 0, j = i;\n                \n                // Parse the multiplier after the closing parenthesis\n                if (i < n && isdigit(s[i])) {\n                    for (j = i; j < n; j++) {\n                        if (isdigit(s[j])) {\n                            count = count * 10 + (s[j] - \'0\');\n                        } else {\n                            break;\n                        }\n                    }\n                }\n                \n                // Apply the multiplier to the current map\n                if (count) {\n                    for (auto& it : t) {\n                        it.second *= count;\n                    }\n                    i = j - 1;\n                }\n                \n                // Merge the current map into the previous map\n                for (auto& it : t) {\n                    prev_map[it.first] += it.second;\n                }\n                return i - 1;\n            }\n        }\n        \n        // Merge the final map into the previous map\n        for (auto& it : t) {\n            prev_map[it.first] += it.second;\n        }\n        return i;\n    }\n\n    string countOfAtoms(string formula) {\n        int n = formula.size();\n        map<string, int> m;\n        \n        // Solve the formula and build the element count map\n        solve(0, formula, n, m);\n        \n        // Build the result string from the element count map\n        string res;\n        for (auto& it : m) {\n            res += it.first;\n            if (it.second != 1) {\n                res += to_string(it.second);\n            }\n        }\n        return res;\n    }\n};\n```\n```java []\nimport java.util.Map;\nimport java.util.TreeMap;\n\nclass Solution {\n    public int solve(int i, String s, int n, Map<String, Integer> prev_map) {\n        Map<String, Integer> t = new TreeMap<>();\n        \n        for (; i < n; i++) {\n            if (s.charAt(i) == \'(\') {\n                i = solve(i + 1, s, n, t);\n            } else if (Character.isUpperCase(s.charAt(i))) {\n                StringBuilder temp = new StringBuilder();\n                temp.append(s.charAt(i));\n                i++;\n                \n                if (i < n && Character.isLowerCase(s.charAt(i))) {\n                    temp.append(s.charAt(i));\n                    i++;\n                }\n                \n                int count = 0, j;\n                for (j = i; j < n; j++) {\n                    if (Character.isDigit(s.charAt(j))) {\n                        count = count * 10 + (s.charAt(j) - \'0\');\n                    } else {\n                        break;\n                    }\n                }\n                \n                t.put(temp.toString(), t.getOrDefault(temp.toString(), 0) + (count == 0 ? 1 : count));\n                i = (count == 0) ? i - 1 : j - 1;\n            } else if (s.charAt(i) == \')\') {\n                i++;\n                int count = 0, j = i;\n                \n                if (i < n && Character.isDigit(s.charAt(i))) {\n                    for (j = i; j < n; j++) {\n                        if (Character.isDigit(s.charAt(j))) {\n                            count = count * 10 + (s.charAt(j) - \'0\');\n                        } else {\n                            break;\n                        }\n                    }\n                }\n                \n                if (count > 0) {\n                    for (Map.Entry<String, Integer> entry : t.entrySet()) {\n                        entry.setValue(entry.getValue() * count);\n                    }\n                    i = j - 1;\n                }\n                \n                for (Map.Entry<String, Integer> entry : t.entrySet()) {\n                    prev_map.put(entry.getKey(), prev_map.getOrDefault(entry.getKey(), 0) + entry.getValue());\n                }\n                return i - 1;\n            }\n        }\n        \n        for (Map.Entry<String, Integer> entry : t.entrySet()) {\n            prev_map.put(entry.getKey(), prev_map.getOrDefault(entry.getKey(), 0) + entry.getValue());\n        }\n        return i;\n    }\n\n    public String countOfAtoms(String formula) {\n        int n = formula.length();\n        Map<String, Integer> m = new TreeMap<>();\n        \n        solve(0, formula, n, m);\n        \n        StringBuilder res = new StringBuilder();\n        for (Map.Entry<String, Integer> entry : m.entrySet()) {\n            res.append(entry.getKey());\n            if (entry.getValue() != 1) {\n                res.append(entry.getValue());\n            }\n        }\n        return res.toString();\n    }\n}\n```\n```Python []\nclass Solution:\n    def solve(self, i, s, n, prev_map):\n        t = {}\n        \n        while i < n:\n            if s[i] == \'(\':\n                i = self.solve(i + 1, s, n, t)\n            elif s[i].isupper():\n                temp = s[i]\n                i += 1\n                \n                if i < n and s[i].islower():\n                    temp += s[i]\n                    i += 1\n                \n                count = 0\n                while i < n and s[i].isdigit():\n                    count = count * 10 + int(s[i])\n                    i += 1\n                \n                t[temp] = t.get(temp, 0) + (count if count != 0 else 1)\n                i -= 1\n            elif s[i] == \')\':\n                i += 1\n                count = 0\n                while i < n and s[i].isdigit():\n                    count = count * 10 + int(s[i])\n                    i += 1\n                \n                if count > 0:\n                    for key in t:\n                        t[key] *= count\n                    i -= 1\n                \n                for key in t:\n                    prev_map[key] = prev_map.get(key, 0) + t[key]\n                return i - 1\n            i += 1\n        \n        for key in t:\n            prev_map[key] = prev_map.get(key, 0) + t[key]\n        return i\n\n    def countOfAtoms(self, formula):\n        n = len(formula)\n        m = {}\n        \n        self.solve(0, formula, n, m)\n        \n        res = []\n        for key in sorted(m.keys()):\n            res.append(key)\n            if m[key] != 1:\n                res.append(str(m[key]))\n        return \'\'.join(res)\n```\n\n
['Hash Table', 'String', 'Stack', 'C++', 'Java', 'Python3']