✅💯🔥Explanations No One Will Give You🎓🧠Very Detailed Approach🎯🔥Extremely Simple And Effective🔥
\n        \n            \n                Making better choices takes work. There is a daily give and take, but it is worth the effort.\n                    \n 
<blockquote>\n        <p>\n            <b>\n                Making better choices takes work. There is a daily give and take, but it is worth the effort.\n            </b>        \n        </p>\n        <p>\n            --- Tom Rath ---\n        </p>\n</blockquote>\n\n# \uD83D\uDC51Problem Explanation and Understanding:\n\n## \uD83C\uDFAF Problem Description\nYou are given a string `formula` which represents some valid chemical formula. Your task sounds very easy - you need to count chemical elements in this string (for details look description)\n\n## \uD83D\uDCE5\u2935\uFE0F Input:\n- String array `formula` representing a valid chemical formula \n\n## \uD83D\uDCE4\u2934\uFE0F Output:\nCounted elements as new string sorted by elements\' names (element followed by irs number in formula)\n\n---\n\n# 1\uFE0F\u20E3\uD83E\uDDE0 Approach: Stack Of Hashmaps\n\n# \uD83E\uDD14 Intuition\nThis problem just blew my mind. At first glance it seems like an easy task, but when you think about implementation...\n- First of all, when problem asks you to process some string which contains brackets it\'s already a good tip for using stack.\n- But what we want to store in stack? Since in one pair of brackets we can have multiple elements and since we want to somehow efficiently count them and multiply counters if we find multiplier after bracket it\'s a good choice to store every "pair of bracket" in stack as a hashmap (dictionary) where key is element\'s name and value is its counter for current bracket.\n- Let\'s think about how we want to process characters in the `formula`:\n    - First of all, as long as character we\'re considering now is not `"(" or ")"` we understand that we\'re looking at normal formula without brackets, so we will jave only letters and numbers. But where we want to add this counters? If are currently not in bracket then we want to add this counter to final result, in the other case we want to add this counter to the LAST pair of brackets we founded (this is idea behind using stack)\n    - If we found `"("` all we want to do is to add new element in the stack -> just append empty hashmap to the stack.\n    - If we found `")"` we know for sure that we have at least one element in stack. We want to parse multiplier for this bracket if it exists and then add counter multiplied by multiplier to the:\n        - Result hashmap if there\'s no more elements in stack (this was one-level nesting and we ended up in normal formula without brackets)\n        - Hashmap in stack that was before this, since that means that this pair of brackets was nested in some other pair\n- After we counted all elements in result hashmap we want to sort them and create string as required in problem statement\n\n# \uD83D\uDC69\uD83C\uDFFB\u200D\uD83D\uDCBB Coding \n\n- Initialize `result_counter` as an empty dictionary to store the counts of each element.\n- Initialize `parenthesis_stack` as an empty list to store dictionaries for counts of elements inside parentheses.\n- Initialize `cur_ind` to 0 to serve as the current index while iterating through the formula.\n\n- Start a while loop that runs until `cur_ind` is less than `n`.\n- If `cur_char` is an opening parenthesis `(`:\n  - Increment `cur_ind` by 1.\n  - Append an empty dictionary to `parenthesis_stack`.\n- If `cur_char` is a closing parenthesis `)`:\n  - Initialize `mult` as an empty string to store the multiplier.\n  - Increment `cur_ind` by 1.\n  - While the current character is a digit, append it to `mult` and increment `cur_ind`.\n  - Pop the last dictionary from `parenthesis_stack` into `last_counter`.\n  - Set `target` to the last dictionary in `parenthesis_stack` if it exists, otherwise set it to `result_counter`.\n  - For each element and count in `last_counter`, add the count multiplied by `mult` (or 1 if `mult` is empty) to the corresponding count in `target`.\n- If `cur_char` is not any of brackets:\n    - Initialize `cur_elem` as an empty string to store the current element.\n    - Initialize `cur_counter` as an empty string to store the current element\'s count.\n    - Set `target` to the last dictionary in `parenthesis_stack` if it exists, otherwise set it to `result_counter`.\n    - While the current character is not a parenthesis and the index is within bounds:\n        - If the character is an alphabet:\n            - If the character is uppercase and `cur_elem` is not empty, add `cur_elem` to `target` with its count.\n            - Reset `cur_counter` and `cur_elem`.\n            - Append the character to `cur_elem`.\n        - Otherwise, append the character to `cur_counter`.\n        - Increment `cur_ind` by 1 and update `cur_char`.\n    - Add the last element and its count to `target`.\n- Construct the output by joining element names and their counts (if greater than 1) sorted by element names.\n- Return the resulting string.\n\n# \uD83D\uDCD8 Complexity Analysis\n- \u23F0 Time complexity: O(n^2), since at the end we use sorting (n log n), but in the loop we constantly readding characters from hashmap to hashmap and in the worst case we will do this `n // 2` times with every hashmap containing up to `n - (number of brackets` so in total this result in `O(n^2)` TC\n- \uD83E\uDDFA Space complexity: O(n), since `stack` will have size up to `n // 2` -> O(n)\n\n# \uD83D\uDCBB Code\n``` python []\nclass Solution:\n    def countOfAtoms(self, formula: str) -> str:\n        # will contain hash-maps with count of elements in last meeted brackets\n        n: int = len(formula)\n        result_counter: dict[str, int] = {}\n        parenthesis_stack: list[dict[str, int]] = []\n        cur_ind = 0\n\n        while cur_ind < n:\n            cur_char: str = formula[cur_ind]\n\n            if cur_char == "(":\n                cur_ind += 1\n                parenthesis_stack.append({})\n                continue\n\n            if cur_char == ")":\n                mult: str = ""\n                cur_ind += 1\n\n                while cur_ind < n and formula[cur_ind].isdigit():\n                    mult += formula[cur_ind]\n                    cur_ind += 1\n\n                last_counter: dict[str, int] = parenthesis_stack.pop()\n                target: dict[str, int] = parenthesis_stack[-1] if parenthesis_stack else result_counter\n                for elem, counter in last_counter.items():\n                    if elem not in target:\n                        target[elem] = 0\n                    target[elem] += counter * (int(mult) if mult else 1)\n                continue\n\n            cur_elem: str = ""\n            cur_counter: str = ""\n            target: dict[str, int] = parenthesis_stack[-1] if parenthesis_stack else result_counter\n\n            while cur_ind < n and cur_char not in "()":\n                if cur_char.isalpha():\n                    if cur_char.isupper() and cur_elem != "":\n                        if not cur_elem in target:\n                            target[cur_elem] = 0\n                        target[cur_elem] += int(cur_counter) if cur_counter else 1\n                        cur_counter = ""\n                        cur_elem = ""\n                    cur_elem += cur_char\n                else:\n                    cur_counter += cur_char\n                cur_ind += 1\n                if cur_ind != n:\n                    cur_char = formula[cur_ind]\n\n            target = parenthesis_stack[-1] if parenthesis_stack else result_counter\n            if not cur_elem in target:\n                target[cur_elem] = 0\n            target[cur_elem] += int(cur_counter) if cur_counter else 1\n\n        parts: list[str] = [\n            elem + str(counter) if not counter == 1 else elem for elem, counter in result_counter.items()\n        ]\n        parts.sort()\n\n        return "".join(parts)\n```\n``` C++ []\nclass Solution {\npublic:\n    string countOfAtoms(string formula) {\n        int n = formula.length();\n        unordered_map<string, int> result_counter;\n        stack<unordered_map<string, int>> parenthesis_stack;\n        int cur_ind = 0;\n\n        while (cur_ind < n) {\n            char cur_char = formula[cur_ind];\n\n            if (cur_char == \'(\') {\n                cur_ind++;\n                parenthesis_stack.push(unordered_map<string, int>());\n                continue;\n            }\n\n            if (cur_char == \')\') {\n                string mult_str = "";\n                cur_ind++;\n\n                while (cur_ind < n && isdigit(formula[cur_ind])) {\n                    mult_str += formula[cur_ind];\n                    cur_ind++;\n                }\n\n                int mult = mult_str.empty() ? 1 : stoi(mult_str);\n                unordered_map<string, int> last_counter = parenthesis_stack.top();\n                parenthesis_stack.pop();\n                unordered_map<string, int>& target = parenthesis_stack.empty() ? result_counter : parenthesis_stack.top();\n                \n                for (const auto& [elem, counter] : last_counter) {\n                    target[elem] += counter * mult;\n                }\n                continue;\n            }\n\n            string cur_elem = "";\n            string cur_counter_str = "";\n            unordered_map<string, int>& target = parenthesis_stack.empty() ? result_counter : parenthesis_stack.top();\n\n            while (cur_ind < n && formula[cur_ind] != \'(\' && formula[cur_ind] != \')\') {\n                if (isalpha(formula[cur_ind])) {\n                    if (isupper(formula[cur_ind]) && !cur_elem.empty()) {\n                        target[cur_elem] += cur_counter_str.empty() ? 1 : stoi(cur_counter_str);\n                        cur_elem = "";\n                        cur_counter_str = "";\n                    }\n                    cur_elem += formula[cur_ind];\n                } else {\n                    cur_counter_str += formula[cur_ind];\n                }\n                cur_ind++;\n            }\n\n            target[cur_elem] += cur_counter_str.empty() ? 1 : stoi(cur_counter_str);\n        }\n\n        vector<string> parts;\n        for (const auto& [elem, counter] : result_counter) {\n            parts.push_back(elem + (counter == 1 ? "" : to_string(counter)));\n        }\n        sort(parts.begin(), parts.end());\n\n        string result;\n        for (const auto& part : parts) {\n            result += part;\n        }\n\n        return result;\n    }\n};\n```\n``` JavaScript []\nvar countOfAtoms = function(formula) {\n    const n = formula.length;\n    const resultCounter = {};\n    const parenthesisStack = [];\n    let curInd = 0;\n\n    while (curInd < n) {\n        let curChar = formula[curInd];\n\n        if (curChar === \'(\') {\n            curInd++;\n            parenthesisStack.push({});\n            continue;\n        }\n\n        if (curChar === \')\') {\n            let multStr = \'\';\n            curInd++;\n\n            while (curInd < n && isDigit(formula[curInd])) {\n                multStr += formula[curInd];\n                curInd++;\n            }\n\n            const mult = multStr === \'\' ? 1 : parseInt(multStr, 10);\n            const lastCounter = parenthesisStack.pop();\n            const target = parenthesisStack.length === 0 ? resultCounter : parenthesisStack[parenthesisStack.length - 1];\n            \n            for (const [elem, counter] of Object.entries(lastCounter)) {\n                if (!(elem in target)) {\n                    target[elem] = 0;\n                }\n                target[elem] += counter * mult;\n            }\n            continue;\n        }\n\n        let curElem = \'\';\n        let curCounterStr = \'\';\n        let target = parenthesisStack.length === 0 ? resultCounter : parenthesisStack[parenthesisStack.length - 1];\n\n        while (curInd < n && formula[curInd] !== \'(\' && formula[curInd] !== \')\') {\n            if (isAlpha(formula[curInd])) {\n                if (isUpper(formula[curInd]) && curElem !== \'\') {\n                    if (!(curElem in target)) {\n                        target[curElem] = 0;\n                    }\n                    target[curElem] += curCounterStr === \'\' ? 1 : parseInt(curCounterStr, 10);\n                    curElem = \'\';\n                    curCounterStr = \'\';\n                }\n                curElem += formula[curInd];\n            } else {\n                curCounterStr += formula[curInd];\n            }\n            curInd++;\n        }\n\n        if (!(curElem in target)) {\n            target[curElem] = 0;\n        }\n        target[curElem] += curCounterStr === \'\' ? 1 : parseInt(curCounterStr, 10);\n    }\n\n    const parts = [];\n    for (const [elem, counter] of Object.entries(resultCounter)) {\n        parts.push(elem + (counter === 1 ? \'\' : counter));\n    }\n    parts.sort();\n\n    return parts.join(\'\');\n};\n\nfunction isDigit(char) {\n    return char >= \'0\' && char <= \'9\';\n}\n\nfunction isAlpha(char) {\n    return char.toLowerCase() !== char.toUpperCase();\n}\n\nfunction isUpper(char) {\n    return char === char.toUpperCase();\n}\n```\n``` Java []\nclass Solution {\n    public String countOfAtoms(String formula) {\n        int n = formula.length();\n        Map<String, Integer> result_counter = new HashMap<>();\n        Deque<Map<String, Integer>> parenthesis_stack = new ArrayDeque<>();\n        int cur_ind = 0;\n\n        while (cur_ind < n) {\n            char cur_char = formula.charAt(cur_ind);\n\n            if (cur_char == \'(\') {\n                cur_ind++;\n                parenthesis_stack.push(new HashMap<>());\n                continue;\n            }\n\n            if (cur_char == \')\') {\n                StringBuilder mult_str = new StringBuilder();\n                cur_ind++;\n\n                while (cur_ind < n && Character.isDigit(formula.charAt(cur_ind))) {\n                    mult_str.append(formula.charAt(cur_ind));\n                    cur_ind++;\n                }\n\n                int mult = mult_str.length() == 0 ? 1 : Integer.parseInt(mult_str.toString());\n                Map<String, Integer> last_counter = parenthesis_stack.pop();\n                Map<String, Integer> target = parenthesis_stack.isEmpty() ? result_counter : parenthesis_stack.peek();\n                \n                for (Map.Entry<String, Integer> entry : last_counter.entrySet()) {\n                    target.put(entry.getKey(), target.getOrDefault(entry.getKey(), 0) + entry.getValue() * mult);\n                }\n                continue;\n            }\n\n            StringBuilder cur_elem = new StringBuilder();\n            StringBuilder cur_counter_str = new StringBuilder();\n            Map<String, Integer> target = parenthesis_stack.isEmpty() ? result_counter : parenthesis_stack.peek();\n\n            while (cur_ind < n && formula.charAt(cur_ind) != \'(\' && formula.charAt(cur_ind) != \')\') {\n                if (Character.isAlphabetic(formula.charAt(cur_ind))) {\n                    if (Character.isUpperCase(formula.charAt(cur_ind)) && cur_elem.length() > 0) {\n                        target.put(cur_elem.toString(), target.getOrDefault(cur_elem.toString(), 0) + (cur_counter_str.length() == 0 ? 1 : Integer.parseInt(cur_counter_str.toString())));\n                        cur_elem = new StringBuilder();\n                        cur_counter_str = new StringBuilder();\n                    }\n                    cur_elem.append(formula.charAt(cur_ind));\n                } else {\n                    cur_counter_str.append(formula.charAt(cur_ind));\n                }\n                cur_ind++;\n            }\n\n            target.put(cur_elem.toString(), target.getOrDefault(cur_elem.toString(), 0) + (cur_counter_str.length() == 0 ? 1 : Integer.parseInt(cur_counter_str.toString())));\n        }\n\n        List<String> parts = new ArrayList<>();\n        for (Map.Entry<String, Integer> entry : result_counter.entrySet()) {\n            parts.add(entry.getKey() + (entry.getValue() == 1 ? "" : entry.getValue()));\n        }\n        Collections.sort(parts);\n\n        StringBuilder result = new StringBuilder();\n        for (String part : parts) {\n            result.append(part);\n        }\n\n        return result.toString();\n    }\n}\n```\n``` C []\n#define MAX_ELEMENTS 1000\n\ntypedef struct {\n    char element[3];\n    int count;\n} Element;\n\ntypedef struct {\n    Element elements[MAX_ELEMENTS];\n    int size;\n} Counter;\n\ntypedef struct {\n    Counter stack[MAX_ELEMENTS];\n    int top;\n} Stack;\n\nvoid initCounter(Counter* counter) {\n    counter->size = 0;\n}\n\nvoid addElement(Counter* counter, const char* element, int count) {\n    for (int i = 0; i < counter->size; ++i) {\n        if (strcmp(counter->elements[i].element, element) == 0) {\n            counter->elements[i].count += count;\n            return;\n        }\n    }\n    strcpy(counter->elements[counter->size].element, element);\n    counter->elements[counter->size].count = count;\n    counter->size++;\n}\n\nvoid multiplyCounter(Counter* counter, int factor) {\n    for (int i = 0; i < counter->size; ++i) {\n        counter->elements[i].count *= factor;\n    }\n}\n\nvoid mergeCounters(Counter* target, const Counter* source) {\n    for (int i = 0; i < source->size; ++i) {\n        addElement(target, source->elements[i].element, source->elements[i].count);\n    }\n}\n\nvoid push(Stack* stack, const Counter* counter) {\n    stack->stack[++stack->top] = *counter;\n}\n\nCounter pop(Stack* stack) {\n    return stack->stack[stack->top--];\n}\n\nint compareElements(const void* a, const void* b) {\n    return strcmp(((Element*)a)->element, ((Element*)b)->element);\n}\n\nchar* countOfAtoms(char* formula) {\n    int n = strlen(formula);\n    Counter resultCounter;\n    initCounter(&resultCounter);\n    Stack parenthesisStack;\n    parenthesisStack.top = -1;\n    int curInd = 0;\n\n    while (curInd < n) {\n        char curChar = formula[curInd];\n\n        if (curChar == \'(\') {\n            curInd++;\n            Counter newCounter;\n            initCounter(&newCounter);\n            push(&parenthesisStack, &newCounter);\n            continue;\n        }\n\n        if (curChar == \')\') {\n            char mult[10] = "";\n            curInd++;\n\n            while (curInd < n && isdigit(formula[curInd])) {\n                strncat(mult, &formula[curInd], 1);\n                curInd++;\n            }\n\n            int multiplier = mult[0] ? atoi(mult) : 1;\n            Counter lastCounter = pop(&parenthesisStack);\n            multiplyCounter(&lastCounter, multiplier);\n            Counter* target = parenthesisStack.top >= 0 ? &parenthesisStack.stack[parenthesisStack.top] : &resultCounter;\n            mergeCounters(target, &lastCounter);\n            continue;\n        }\n\n        char curElem[3] = "";\n        char curCounter[10] = "";\n        Counter* target = parenthesisStack.top >= 0 ? &parenthesisStack.stack[parenthesisStack.top] : &resultCounter;\n\n        while (curInd < n && formula[curInd] != \'(\' && formula[curInd] != \')\') {\n            if (isalpha(formula[curInd])) {\n                if (isupper(formula[curInd]) && curElem[0] != \'\\0\') {\n                    addElement(target, curElem, curCounter[0] ? atoi(curCounter) : 1);\n                    curCounter[0] = \'\\0\';\n                    curElem[0] = \'\\0\';\n                }\n                strncat(curElem, &formula[curInd], 1);\n            } else {\n                strncat(curCounter, &formula[curInd], 1);\n            }\n            curInd++;\n        }\n\n        addElement(target, curElem, curCounter[0] ? atoi(curCounter) : 1);\n    }\n\n    qsort(resultCounter.elements, resultCounter.size, sizeof(Element), compareElements);\n\n    char* result = malloc(MAX_ELEMENTS * 10);\n    result[0] = \'\\0\';\n    for (int i = 0; i < resultCounter.size; ++i) {\n        strcat(result, resultCounter.elements[i].element);\n        if (resultCounter.elements[i].count > 1) {\n            char countStr[10];\n            sprintf(countStr, "%d", resultCounter.elements[i].count);\n            strcat(result, countStr);\n        }\n    }\n\n    return result;\n}\n```\n\n## \uD83D\uDCA1\uD83D\uDCA1\uD83D\uDCA1I encourage you to check out [my profile](https://leetcode.com/heir-of-god/) and [Project-S](https://github.com/Heir-of-God/Project-S) project for detailed explanations and code for different problems (not only Leetcode). Happy coding and learning!\uD83D\uDCDA\n\n### Please consider *upvote*\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F because I try really hard not just to put here my code and rewrite testcase to show that it works but explain you WHY it works and HOW. Thank you\u2764\uFE0F\n\n## If you have any doubts or questions feel free to ask them in comments. I will be glad to help you with understanding\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\n\n![There is image for upvote](https://assets.leetcode.com/users/images/fde74702-a4f6-4b9f-95f2-65fa9aa79c48_1716995431.3239644.png)\n
['Hash Table', 'String', 'Stack', 'C', 'Sorting', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']