💯✅🔥Detailed Easy Java ,Python3 ,C++ Solution|| 3 ms ||≧◠‿◠≦✌
Approach(Java)\n\nThe approach used in the given code is to parse the chemical formula string from right to left, keeping track of the current multiplier and us
# Approach(Java)\n\nThe approach used in the given code is to parse the chemical formula string from right to left, keeping track of the current multiplier and using a stack to handle nested parentheses. The code maintains a `TreeMap` `res` to store the count of each atom.\n\n---\n\n# Intuition\n\nThe intuition behind the approach is to process the formula from right to left, considering the following cases:\n\n1. If the current character is a closing parenthesis, we divide the current multiplier by the value popped from the stack.\n2. If the current character is a digit, we find the complete number and push it onto the stack, updating the multiplier accordingly.\n3. If the current character is an uppercase letter, we find the complete element name and update the count in the `res` map.\n\n---\n\n## Time Complexity\n\nThe time complexity of the given code is O(n), where n is the length of the input formula string. This is because we iterate through the string once, processing each character.\n\n---\n\n## Space Complexity\n\nThe space complexity is O(n), where n is the number of unique atoms in the formula. This is because we store the count of each atom in the `res` map, and the size of the map is proportional to the number of unique atoms.\n\n---\n\n## Step-by-step Explanation\n\nLet\'s go through the code step by step using the example formula "H2O":\n\n1. Initialize the `res` map, `stack`, and `multiplier` variables.\n\n```\nres = {}\nstack = []\nmultiplier = 1\n```\n\n2. Set `end` to the last index of the formula string and `i` to the last index.\n\n```\nformula = "H2O"\nend = 2\ni = 2\n```\n\n3. While `i` is greater than or equal to 0:\n\n   a. If the character at index `i` is a closing parenthesis, divide the `multiplier` by the value popped from the stack and decrement `i`.\n\n   ```\n   # No closing parenthesis in "H2O"\n   ```\n\n   b. Set `end` to `i`.\n\n   ```\n   end = 2\n   ```\n\n   c. Initialize `val` to 1.\n\n   ```\n   val = 1\n   ```\n\n   d. If the character at index `i` is a digit, find the complete number by moving `i` to the left until a non-digit character is encountered, parse the number, and set `val` accordingly.\n\n   ```\n   # Character at index 2 is \'2\'\n   i = 1\n   val = 2\n   ```\n\n   e. Push `val` onto the stack and multiply `multiplier` by `val`.\n\n   ```\n   stack = [2]\n   multiplier = 2\n   ```\n\n   f. Set `end` to `i`.\n\n   ```\n   end = 1\n   ```\n\n   g. If the character at index `i` is an uppercase letter, move `i` to the left until a lowercase letter or non-letter character is encountered, and call the `updateMap` function with the extracted element name.\n\n   ```\n   # Character at index 1 is \'H\'\n   i = 0\n   updateMap(\'H\')\n   ```\n\n   h. Decrement `i`.\n\n   ```\n   i = 0\n   ```\n\n4. Create a `StringBuilder` `rs`.\n\n```\nrs = StringBuilder()\n```\n\n5. Iterate through the `res` map:\n\n   a. Append the key (element name) to `rs`.\n   b. If the value (count) is greater than 1, append the value to `rs`.\n\n   ```\n   res = {\'H\': 1, \'O\': 1}\n   rs = "H1O1"\n   ```\n\n6. Return the `rs` string.\n\n```\nreturn "H2O"\n```\n\nThe final result is "H2O".\n\n\n---\n\n# Approach and Intuition(Python3):\n\nThe problem is to count the atoms in a chemical formula. The formula is given as a string, and the goal is to return a string representing the atoms and their counts. The approach involves parsing the formula, identifying atoms and their counts, and then combining the atoms with their counts in the final output.\n\n---\n\n# Time Complexity:\n\nThe time complexity of this solution is O(n), where n is the length of the input string. This is because the solution iterates over the input string once to parse it and then again to sort the atoms and their counts.\n\n---\n# Space Complexity:\n\nThe space complexity is O(n), where n is the length of the input string. This is because the solution needs to store the parsed atoms and their counts in a dictionary and then sort them.\n\n---\n\n# Step-by-Step Explanation with Example:\n\nLet\'s use the string "H2O" as an example to explain the solution step by step:\n\n1. **Initial Parsing:**\n   - The input string "H2O" is parsed into individual characters.\n   - The characters are stored in an array `arr`.\n\n   ```python\n   arr = ["H", "2", "O"]\n   ```\n\n2. **Identifying Atoms and Counts:**\n   - The array `arr` is iterated over to identify atoms and their counts.\n   - Atoms are identified by their letters (e.g., "H", "O").\n   - Counts are identified by the numbers that follow the atoms (e.g., "2" for "H2").\n\n   ```python\n   newarr = [("H", 2), ("O", 1)]\n   ```\n\n3. **Sorting Atoms and Counts:**\n   - The `newarr` array is sorted based on the atoms and their counts.\n   - This ensures that the atoms are in alphabetical order and their counts are in descending order.\n\n   ```python\n   newarr = [("H", 2), ("O", 1)]\n   ```\n\n4. **Constructing the Final Output:**\n   - The sorted `newarr` array is used to construct the final output string.\n   - Each atom is appended to the output string, followed by its count if it is greater than 1.\n\n   ```python\n   tt = "H2O"\n   ```\n\n5. **Final Output:**\n   - The final output string is returned.\n\n   ```python\n   return "H2O"\n   ```\n\nThis solution effectively parses the chemical formula, identifies atoms and their counts, sorts them, and constructs the final output string.\n\n---\n\n# Approach(C++)\n\nThe approach used in the given C++ code is similar to the Java solution. We parse the chemical formula string from right to left, keeping track of the current multiplier and using a stack to handle nested parentheses. The code maintains an `unordered_map` `res` to store the count of each atom.\n\n---\n\n# Intuition\n\nThe intuition behind the approach is the same as the Java solution. We process the formula from right to left, considering the following cases:\n\n1. If the current character is a closing parenthesis, we push the current multiplier to the stack.\n2. If the current character is an opening parenthesis, we divide the multiplier by the value popped from the stack.\n3. If the current character is a digit, we find the complete number and update the multiplier accordingly.\n4. If the current character is an uppercase letter, we find the complete element name and update the count in the `res` map.\n\n---\n# Time Complexity\n\nThe time complexity of the given code is O(n), where n is the length of the input formula string. This is because we iterate through the string once, processing each character.\n\n---\n# Space Complexity\n\nThe space complexity is O(n), where n is the number of unique atoms in the formula. This is because we store the count of each atom in the `res` map, and the size of the map is proportional to the number of unique atoms.\n\n---\n## Step-by-step Explanation\n\nLet\'s go through the code step by step using the example formula "H2O":\n\n1. Initialize the `res` map, `st` stack, and `multiplier` variable.\n\n```\nres = {}\nst = []\nmultiplier = 1\n```\n\n2. Iterate through the formula from right to left:\n\n   a. If the current character is \')\', push the current `multiplier` to the stack.\n\n   ```\n   formula = "H2O"\n   i = 2\n   c = \'O\'\n   # No closing parenthesis, so no changes\n   ```\n\n   b. If the current character is \'(\', divide the `multiplier` by the value popped from the stack.\n\n   ```\n   # No opening parenthesis, so no changes\n   ```\n\n   c. If the current character is a digit, find the complete number and update the `multiplier`.\n\n   ```\n   # Character at index 2 is \'2\'\n   i = 1\n   c = \'2\'\n   multiplier = 2\n   ```\n\n   d. If the current character is an uppercase letter, find the complete element name and update the `res` map.\n\n   ```\n   # Character at index 1 is \'H\'\n   i = 0\n   c = \'H\'\n   res[\'H\'] += multiplier = 2\n   ```\n\n3. Build the final result string by iterating through the `res` map and appending the element name and count (if greater than 1) to the result.\n\n```\nres = {\'H\': 2, \'O\': 1}\nresult = "H2O"\n```\n\n4. Return the final result string.\n\n```\nreturn "H2O"\n```\n\nThe final result is "H2O".\n\nThe visualization of the step-by-step process can be represented as follows:\n\n```\nInitial state:\nres = {}\nst = []\nmultiplier = 1\n\nIterate through the formula "H2O" from right to left:\n\ni = 2, c = \'O\'\n# No changes\n\ni = 1, c = \'2\'\nmultiplier = 2\n\ni = 0, c = \'H\'\nres[\'H\'] += multiplier = 2\n\nFinal state:\nres = {\'H\': 2, \'O\': 1}\nresult = "H2O"\n```\n\nThe key steps are:\n1. Handling the digit \'2\' to update the multiplier.\n2. Handling the uppercase letter \'H\' to update the count in the `res` map.\n3. Building the final result string by iterating through the `res` map.\n\n ---\n\n\n![upvote.png](https://assets.leetcode.com/users/images/7a4319bd-c377-4c83-80ff-e7bb91ae2269_1720925857.1245637.png)\n\n```java []\nclass Solution {\n    Map<String, Integer> res = new TreeMap<>();\n    Stack<Integer> stack = new Stack<>();\n    int multiplier = 1;\n    \n    public String countOfAtoms(String formula) {\n        int end = formula.length() - 1, i = formula.length() - 1;\n        \n        while (i >= 0) {\n            if (formula.charAt(i) == \'(\') {\n                multiplier /= stack.pop();\n                i--;\n                continue;\n            }\n            \n            end = i;\n            int val = 1;\n            \n            if (Character.isDigit(formula.charAt(i))) {\n                while (Character.isDigit(formula.charAt(i))) i--;\n                val = Integer.parseInt(formula.substring(i+1, end+1));\n            } \n            stack.push(val);\n            multiplier *= val;\n            \n            end = i;\n            if (Character.isLetter(formula.charAt(i))) {\n                while(Character.isLowerCase(formula.charAt(i))) i--;\n                updateMap(formula.substring(i, end+1));\n            }\n            i--;\n        }\n        \n        StringBuilder rs = new StringBuilder();\n        for (Map.Entry<String, Integer> entry : res.entrySet()) {\n            rs.append(entry.getKey());\n            if (entry.getValue() > 1) rs.append(entry.getValue());\n        }\n        return rs.toString();\n    }\n    \n    private void updateMap(String key) {\n        if (res.get(key) == null) {\n            res.put(key, multiplier);\n        } else {\n            res.put(key, multiplier + res.get(key));\n        }\n\n        multiplier /= stack.pop();\n    }\n}\n```\n```python3 []\nclass Solution:\n    def countOfAtoms(self, formula: str) -> str:\n\n        tt=""\n        arr=[]\n        temp=""\n        for i in range(0,len(formula)):\n            cu=formula[i]\n\n            if temp=="":\n                temp+=cu\n                continue\n            if cu=="(" or cu==")":\n                if temp!="":\n                    arr.append(temp)\n                arr.append(cu)\n                temp=""\n                continue\n            \n            if temp.isnumeric():\n                if cu.isnumeric():\n                    temp+=cu\n                else:\n                    arr.append(temp)\n                    temp=cu\n            else:\n                if cu.isnumeric():\n                    arr.append(temp)\n                    temp=cu\n                else:\n                    if cu.isupper():\n                        arr.append(temp)\n                        temp=cu\n                    else:\n                        temp+=cu\n        if temp!="":\n            arr.append(temp)\n       \n        newarr=[]\n        i=0\n        while i<len(arr):\n            cu=arr[i]\n            if cu=="(":\n                newarr.append((cu,0))\n                \n            elif cu==")":\n                \n                nexta=1\n                if i+1<len(arr):\n                    temp=arr[i+1]\n                    if temp.isnumeric():\n                        nexta=int(temp)\n                        i+=1\n                temparr=[]\n                while len(newarr)>0 and newarr[-1][0]!="(":\n                    f,c=newarr.pop()\n                    temparr.append((f,c*nexta))\n                newarr.pop()\n                for k in range(0,len(temparr)):\n                    newarr.append(temparr[k])\n            elif cu.isalpha():\n                nexta=1\n                if i+1<len(arr):\n                    temp=arr[i+1]\n                    if temp.isnumeric():\n                        nexta=int(temp)\n                        i+=1\n                newarr.append((cu,nexta))\n            i+=1\n\n        newarr.sort(key=lambda x:(x[0],x[1]))\n        \n        \n        dicta={}\n       \n        for i in range(0,len(newarr)):\n            f,c=newarr[i]\n            dicta[f]=dicta.get(f,0)+c\n        # print(dicta)\n        for i in range(0,len(newarr)):\n            f,c=newarr[i]\n            if f in dicta:\n                tt+=f\n                if dicta[f]>1:\n                    tt+=str(dicta[f])\n                del dicta[f]\n\n\n        return tt    \n```\n```C++ []\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\n\n---\n\n\n\n\n\n
['Hash Table', 'String', 'Sorting', 'C++', 'Java', 'Python3']