[C++] Linear scan right to left + sorting - O(n) + O(n log n)
Scan the input from right to left and store each atom alongside its count number cnt. The cnt var is reset back to zero each time a new atom is spotted to avoid
Scan the input from right to left and store each atom alongside its count number `cnt`. The `cnt` var is reset back to zero each time a new atom is spotted to avoid the case where a previously counted atom may influence the current count e.g. `"SO3"`. The `mult` is the multiplier used to keep track of the atom groups enclosed in the parenthesis.\n\n```cpp\nclass Solution {\npublic:\n    string countOfAtoms(string exp) {\n        map<string, int> atoms;\n        string ans;\n        int cnt = 0, mult = 1;\n        stack<int> st;\n        \n        for (int i = size(exp) - 1; i >= 0; i--) {\n            if (isalpha(exp[i]) and islower(exp[i])) {\n                int len = 2;\n                i--;\n                \n                while (i >= 0 and islower(exp[i])) {\n                    i--;\n                    len++;\n                }\n                \n                string atom = exp.substr(i, len);\n                atoms[atom] += max(cnt, 1) * mult;\n                cnt = 0;\n            } else if (isalpha(exp[i]) and isupper(exp[i])) {\n                string atom(1, exp[i]);\n                atoms[atom] += max(cnt, 1) * mult;\n                cnt = 0;\n            } else if (isdigit(exp[i])) {\n                cnt = exp[i] - \'0\';\n                int p = 10;\n                \n                while (i - 1 >= 0 and isdigit(exp[i - 1])) {\n                    cnt += p * (exp[--i] - \'0\');\n                    p *= 10;\n                }\n            } else if (exp[i] == \')\') {\n                st.push(mult);\n                mult *= max(cnt, 1);\n                cnt = 0;\n            } else {\n                mult = st.top();\n                st.pop();\n            }\n        }\n        \n        for (auto [atom, count]: atoms) {\n            ans += atom;\n            \n            if (count > 1) {\n                ans += to_string(count);\n            }\n        }\n        \n        return ans;\n    }\n};\n```\n\nTime complexity - O(N log N).\nSpace complexity - O(N).
['C', 'Sorting', 'C++']