🔥 Well Explained Solution🔥 Hard made Easy
Intuition\nIt would have been a way easier problem if () thing wasn\'t there\nJust because of those () we need to figure out a way to find the  actual count of 
# Intuition\nIt would have been a way easier problem if `()` thing wasn\'t there\nJust because of those `()` we need to figure out a way to find the  actual count of a element\n\n# Approach\n- Assume you would not given `H2(MgH2)2` instead \n    `x1 x2  x2`\n    `H2 Mg1 H2`\n    where `xd` factor at the top signifies how much its count will be multiplied due to `()xd` \n    then it can be implemented easily with `map["Mg"] += 1 * 2`\n- So that\'s exactly what our `mult` vector stores\n- What could be the multFactor for a particular element cannot be known in linear time if we iterate from start, that\'s why we will start from end\n- We will get the digit just after the `)` and this will have impact until its matching `(` is found\n- Now why do we need a stack for this can\'t it be done with just a variable \n- Assume this case `(A(BC)2)3` here first our factor will be x3 but after we encounter x2 factor so ultimately `BC` has a factor x6 \nthen as soon as we pass `BC` impact of x2 needs to be undone which we can do by x6/x2\nSimilarly there can be a lot of nested brackets and for them we need a stack to get the correct multFactor for each element\n- Now once we have assigned appropriate multFactors for each of the element(I have only mapped them with their first char i.e uppercase)\nwe are almost done\n- Now we can simply iterate from left to right and just get the string, its digit and we already have the multFactor so just add them up in a map\n- Now just return the answer in the appropriate format\n\n# Complexity\n- Time complexity: $$O(n)$$ (if we don\'t consider the TC of additional requirement of returning in the sorted order)\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        int n = formula.length();\n        vector<int> mult(n, 1);\n        stack<int> factors;\n        int multFactor = 1;\n        for(int i=n-1; i>=0; --i) {\n            char ch = formula[i];\n            if(ch == \')\') {\n                string cnt = "";\n                int k = i+1;\n                while(k<n && isdigit(formula[k])) {\n                    cnt += formula[k++];\n                }\n                if(cnt == "") cnt = "1";\n                int digit = stoi(cnt);\n                factors.push(digit);\n                multFactor *= digit;\n            }\n            else if(ch == \'(\') {\n                int digit = factors.top();\n                factors.pop();\n                multFactor /= digit;\n            }\n            else if(isupper(ch)) {\n                mult[i] = multFactor;\n            }\n            else continue;\n        }\n        map<string, int> res;\n        for(int i=0; i<n; ++i) {\n            char ch = formula[i];\n            if(!isupper(ch)) continue;\n            multFactor = mult[i];\n            string ele = "";\n            ele += ch;\n            int j = i+1;\n            while(j<n && islower(formula[j])) {\n                ele += formula[j++];\n            }\n            string cnt = "";\n            int k = j;\n            while(k<n && isdigit(formula[k])) {\n                cnt += formula[k++];\n            }\n            if(cnt == "") cnt = "1";\n            int digit = stoi(cnt);\n            res[ele] += digit * multFactor;\n            i = k-1;\n        }\n        string ans = "";\n        for(auto &[ele, digit] :res) {\n            string cnt = to_string(digit);\n            if(cnt == "1") cnt = "";\n            ans += ele + cnt;\n        }\n        return ans;\n    }\n};\n```\n\n\nHope you found this helpful\nIf so please do Upvote it\nHappy Coding!!\n\n![leetcode.png](https://assets.leetcode.com/users/images/7a98ada3-fb9b-4413-8538-92fe790f4577_1701070150.1852815.png)
['Stack', 'C++']