Beats 100% | C++ | Simple Iterative Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nIt\'s pretty straight forward.\n\nWe iterate from left to right in the string.\nWe stor
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt\'s pretty straight forward.\n\nWe iterate from left to right in the string.\nWe store the **Atoms** & their **Number** on a **Map<string,int>** `mp`\n\nRecursion will take care of Nested Paranthesis\n\n---\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nStore the Begining & End of each paranthesis in a`Map<int,int>` \nUse Stack for appropriate pairing of indices\n```\nmap<int,int> window; // {start,end} of each paranthesis\nstack<int> st;\nfor(int i=0;i<n;++i){\n    if(s[i]==\'(\') st.push(i);\n    else if(s[i]==\')\'){\n        window[st.top()] = i;\n        st.pop();\n    }\n}\n```\n\n# The Solve function()\nIt returns a Map<string,int> `mp`\nRepresenting the answer for the substring $$a <= i <= b$$\n\nIt initializes an empty string `str` \nIterates the string from $$index=a$$ to $$b$$ (both including)\n\n# **Whenever a character is found**\n\n**If the $$character$$ is Uppercase**\nUpdate `str` to new $$character$$.\nBut if `str` holds $$old character$$\nthen first Update the `map` as $$Number$$ of old character = 1 since 1 is the default $$ Number$$ when not specified\n\n```\nelse if(s[i]>=\'A\' && s[i]<=\'Z\'){\n    if(str!="") mp[str] += 1;\n    str = ""; //clear off prev name\n    str += s[i]; //capital letter\n}\n```\n\n**If the $$character$$ is Lowercase**\nAdd $$character$$ to the existing `str`\n```\nelse if(s[i]>=\'a\' && s[i]<=\'z\') str += s[i];\n```\n\n**If the character is a number**\nConvert the substring to integer using `stoi(string)` and Update `mp`\n`mp[Atom] += Number`\n\n```\nif(s[i]>=\'0\' && s[i]<=\'9\'){\n    int num = stoi(s.substr(i,s.size())); //convert to int\n    if(str.size()) mp[str] += num; \n    str = "";\n}\n```\n# Whenever a paranthesis is found\n\nIf there is an existing $$Atom$$ (from before the beginning of paranthesis) which has NOT been updated on `mp` Then Update it first\n\n```\nif(str.size()){ //test case Mg(H2O)2. marks Mg = 1\n    mp[str] += 1;\n    str = "";\n}\n```\nTreating the Substring Inside the Paranthesis as a string whose answer will be given by the function `solve(start, end)`\nWe apply **Recursion** which calculates the Elements & their Numbers inside the paranthesis and stores it in the Map<string,int>`Temp`\n\n```\nmap<string,int> temp = solve(i+1,window[i]-1,s,window); //Recursion\n```\nThe Elements of the`Temp`must be **Multiplied** by the number following the paranthesis (if any)\n```\nint cnt=1; //multiplies freq of elements inside bracket by cnt\nint close = window[i]+1; //just after the bracket close\nif(close<n && s[close]>=\'0\' && s[close]<=\'9\')\n    cnt = stoi(s.substr(close,n));\nif(cnt>1)\n    for(auto it : temp) temp[it.first] *= cnt;\n```\n\nNow We must add elements of `Temp` into our original Map `mp`\n```\nfor(auto it : temp) //main map me add karo temp\n    mp[it.first] += it.second;\n```\n\nJump to end of bracket\n```\ni = window[i];\n```\n# Iteration ends\nBefore returing the Map `mp` check if there is any residual string which is NOT updated, Update it.\n\n```\nif(str!="") mp[str] += 1;\nreturn mp;\n```\n\n---\nNow our work is done.\nIn the `main()` function\nWe simply print elements of this map `mp` as in the string `res`.\n```\nstring res = "";\nfor(auto it : mp){ //prints the result in string\n    res += it.first;\n    if(it.second>1) res += to_string(it.second);\n}\nreturn res;\n```\n\n---\n\n# Code\n```\nclass Solution {\npublic:\n\n    //start index, end index, main string, indices of start & end of all brackets\n    map<string,int> solve(int a, int b, string &s, map<int,int> &window){ \n        \n        map<string,int> mp;\n        int n = s.size();\n        string str = "";\n        for(int i=a;i<=b;++i){\n            if(s[i]==\'(\'){ //takes care of brackets (...)\n                if(str.size()){ //test case Mg(H2O)2. marks Mg = 1\n                    mp[str] += 1;\n                    str = "";\n                }\n                map<string,int> temp = solve(i+1,window[i]-1,s,window); //recursion\n                \n                int cnt=1; //multiplies freq of elements inside bracket by cnt\n                int close = window[i]+1; //just after the bracket close\n                if(close<n && s[close]>=\'0\' && s[close]<=\'9\') cnt = stoi(s.substr(close,n));\n                if(cnt>1) for(auto it : temp) temp[it.first] *= cnt;\n                \n                for(auto it : temp) //main map me add karo temp\n                    mp[it.first] += it.second;\n                \n                i = window[i]; //jump to end of bracket\n            }\n            else{ //characters\n                if(s[i]>=\'0\' && s[i]<=\'9\'){\n                    int num = stoi(s.substr(i,s.size())); //convert to int\n                    if(str.size()) mp[str] += num; \n                    str = "";\n                }\n                else if(s[i]>=\'a\' && s[i]<=\'z\') str += s[i];\n                else if(s[i]>=\'A\' && s[i]<=\'Z\'){\n                    if(str!="") mp[str] += 1;\n                    str = ""; //clear off prev name\n                    str += s[i]; //capital letter\n                }\n            }\n        }\n        if(str!="") mp[str] += 1;\n        return mp;\n    }\n\n    string countOfAtoms(string s) {\n        int n = s.size();\n        map<int,int> window; // {start,end} of each bracket\n        stack<int> st;\n        for(int i=0;i<n;++i){ //indices of start & end of all brackets\n            if(s[i]==\'(\') st.push(i);\n            else if(s[i]==\')\'){\n                window[st.top()] = i;\n                st.pop();\n            }\n        }\n        map<string,int> mp = solve(0,n-1,s,window) ; //does everything\n\n        string res = "";\n        for(auto it : mp){ //prints the result in string\n            res += it.first;\n            if(it.second>1) res += to_string(it.second);\n        }\n        return res;\n    }\n};\n```\n![Eminem RickRoll YT.png](https://assets.leetcode.com/users/images/65b74299-fe66-4886-bf98-a70d95c936f7_1722563071.432074.png)
['String', 'C++']