Recursion with vector as stack||No hash map, no sorting||0ms beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe implementation is done before LC changed the restriction for the input for unreal t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe implementation is done before LC changed the restriction for the input for unreal testcases; a revised code will be later presented.\n\nThis hard question took me hours to solve. To find an effective linear solution is the goal.\nLC says\n> formula is always valid.\n\nDue to perioid table, every chemical element is denoted by 1~2 letters. https://en.wikipedia.org/wiki/Chemical_element\nUsing this fact simplify the implementation.\n\nSince the unreal custom formula is allowed to input, a hash map version is implemented.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Every chemical element is denoted by 1~2 letters. A size of 27*26 C-array `atom` is sufficient for storing the numbers of all possible atoms. And no need for sorting for the answer format\n2. Function idx converts chemical string to its corresponding index x; function chemi converts x to its corresponding chemical string\n3. The recursive function `void f(int i, string& formula, int l = -1, int r = -1, int times = 1)` counts the atoms\n4. Function `string convert()` onverts atom array to result string\n5. In the function `countOfAtoms(string& formula)` uses the trick of stack to find the pairing parentheses, 3 important info `(pos for right \')\', real ending, multiplier)` (where multiplier is the number within the parentheses sould be multiplied) are stored in the container `mult`\n6. After this is done, call `f(0, formula, 0, n, 1)`\n7. return `convert()`\n8. Since LC has changed the restriction for the input for unreal testcases, a hash map version dealing with more general testcase including all possible unreal testcases is implemented.\n# Mult info for testcase\nThis implementation computes 1st the info for mult for each \'(\',` (pos for right \')\', real ending, multiplier)`\nTestcase `"K4(ON(SO3)2)3(Fe(CN)6)2"` has 4 pairs of brackets.\n```\n2 ->[11,12,3]\n5 ->[9,10,2]\n13 ->[21,22,2]\n16 ->[19,20,6]\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n $$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n $$O(n)$$\n# Code for only  real chemical elements||Recursion with vector as stack C++ 0ms beats 100%\n```\nclass Solution {\npublic:\n    using int3 = array<int, 3>; // (pos for right \')\', real ending, multiplier)\n    vector<int3> mult;\n    int n;\n    int atom[702]; // Array to store counts of each atom\n\n    // Convert chemical formula string to index\n    inline int idx(string& s) {\n        return (s[0] - \'A\') * 27 + ((s.size() == 1) ? 0 : (s[1] - \'a\' + 1));\n    }\n\n    // Convert index to chemical formula string\n    inline string chemi(int x) {\n        auto [q, r] = div(x, 27);\n        string s = string(1, q + \'A\');\n        if (r > 0)\n            s += (r - 1 + \'a\');\n        return s;\n    }\n\n    // Recursive function to count atoms\n    void f(int i, string& formula, int l = -1, int r = -1, int times = 1) {\n        while (i < r) {\n            if (formula[i] == \'(\') {\n                auto& m = mult[i];\n                f(i+1, formula, i+1, m[0], m[2] * times);\n                i = m[1] + 1;\n            } \n            else if (isupper(formula[i])) {\n                string chemi = string(1, formula[i]);\n                int start = i;\n                if (i+1 < r && islower(formula[i+1])) {\n                    chemi+= formula[i+1];\n                    i++;\n                }\n                i++;\n\n                int x = 0;\n                while (i < r && isdigit(formula[i])) {\n                    x=x*10 + (formula[i]-\'0\');\n                    i++;\n                }\n                if (x== 0) x= 1;\n                atom[idx(chemi)]+= x* times;\n            } \n            else \n                i++;\n        }\n    }\n\n    // Convert atom array to result string\n    inline string convert() {\n        string result;\n        for (int i = 0; i < 702; ++i) {\n            if (atom[i] > 0) {\n                result += chemi(i);\n                if (atom[i] > 1)\n                    result += to_string(atom[i]);\n            }\n        }\n        return result;\n    }\n\n    string countOfAtoms(string& formula) {\n        memset(atom, 0, sizeof(atom));\n        n=formula.size();\n\n        vector<int> st;\n        mult.assign(n, {-1, -1, -1});\n        for (int i = 0; i < n; i++) {\n            char c = formula[i];\n            if (c == \'(\')\n                st.push_back(i);\n            else if (c == \')\') {\n                int x = 0, r = i;\n                while (i + 1 < n && isdigit(formula[i + 1])) {\n                    x = 10 * x + (formula[++i] - \'0\');\n                }\n                if (x == 0)\n                    x = 1;\n                int l = st.back();\n                st.pop_back();\n                mult[l] = {r, i, x};\n            }\n        }\n        f(0, formula, 0, n, 1); // Start recursive function\n        return convert();       // Convert the atom array to result string\n    }\n\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n\n```\n# C++ dealing with possible unreal formula by using hash map & sort TC=O(n+k log k) where k= number for chemical elements||0ms beats 100%\n```\nclass Solution {\npublic:\n    using int3 = array<int, 3>; // (pos for right \')\', real ending, multiplier)\n    vector<int3> mult;\n    int n;\n\n    unordered_map<string, int> atom; \n\n    // Recursive function to count atoms TC: O(n)\n    void f(int i, string& formula, int r, int times = 1) {\n        while (i < r) {\n            if (formula[i] == \'(\') {\n                auto& m = mult[i];\n                f(i+1, formula, m[0], m[2] * times);\n                i = m[1]+1;\n            } \n            else if (isupper(formula[i])) {\n                string chemi = string(1, formula[i]);\n                int start = i;\n                while (i+1 < r && islower(formula[i+1])) {\n                    chemi+= formula[i+1];\n                    i++;\n                }\n                i++;\n\n                int x = 0;\n                while (i < r && isdigit(formula[i])) {\n                    x=x*10 + (formula[i]-\'0\');\n                    i++;\n                }\n                if (x== 0) x= 1;\n                atom[chemi]+= x* times;\n            } \n            else \n                i++;\n        }\n    }\n\n    // Print the content of the container\n    void print(auto& c) {\n        int sz=c.size();\n        for (int i=0; i<n; i++){\n            auto& x=c[i];\n            if (x[0]!=-1)\n                cout<<i<<" ->[" << x[0] << "," << x[1] << "," << x[2]<<"]\\n";\n        }\n    }\n\n    // Convert atom to result string TC: O(klog k)\n    inline string convert() {\n        vector<pair<string, int>> satom(atom.begin(),atom.end());\n        sort(satom.begin(), satom.end());\n        string result;\n        for (auto& [chemi, x]: satom) {\n            result += chemi;\n            if (x > 1)\n                result += to_string(x);\n            \n        }\n        return result;\n    }\n\n    string countOfAtoms(string& formula) {\n        n=formula.size();\n        atom.reserve(n);\n        vector<int> st;\n        mult.assign(n, {-1, -1, -1});\n        for (int i = 0; i < n; i++) {// O(n)\n            char c = formula[i];\n            if (c == \'(\')\n                st.push_back(i);\n            else if (c == \')\') {\n                int x = 0, r = i;\n                while (i + 1 < n && isdigit(formula[i + 1])) {\n                    x = 10 * x + (formula[++i] - \'0\');\n                }\n                if (x == 0)\n                    x = 1;\n                int l = st.back();\n                st.pop_back();\n                mult[l] = {r, i, x};\n            }\n        }\n    //    print(mult);\n        \n        f(0, formula, n, 1); // Start recursive function\n        return convert();       // Convert the atom array to result string\n    }\n\n};\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['String', 'Stack', 'Recursion', 'C++']