Beats 100% Java, python
\n\n# Intuition\nThe problem of counting atoms in a chemical formula involves parsing a string that may contain nested structures (parentheses) and numbers. The
\n\n# Intuition\nThe problem of counting atoms in a chemical formula involves parsing a string that may contain nested structures (parentheses) and numbers. The key insight is to process the formula from right to left, which simplifies handling of multipliers and nested structures.\n\n# Approach\n1. Use a TreeMap to store atom counts (automatically sorted).\n2. Process the formula string from right to left.\n3. Use a stack to handle nested parentheses.\n4. Parse different types of characters (lowercase, uppercase, numbers, parentheses) differently.\n5. Build the final string from the sorted TreeMap.\n\n# Complexity\n- Time complexity: O(N), where N is the length of the formula string.\n- Space complexity: O(N), for the TreeMap and stack.\n\n# Code\nLet\'s break down the code in detail:\n\n```java []\nclass Solution {\n    public String countOfAtoms(String formula) {\n        // TreeMap to store atom counts, automatically sorted by atom name\n        TreeMap<String, Integer> map = new TreeMap<>();\n        \n        // Stack to handle nested parentheses, max size 1000 (could be dynamic)\n        int[] stack = new int[1000];\n        int top = 0; // Top of the stack\n        \n        int multiplier = 1; // Current multiplier for atom counts\n        int freq = 0; // Frequency of the current atom\n        \n        // Convert formula to char array for easier processing\n        char[] c = formula.toCharArray();\n        \n        // Process the formula from right to left\n        for(int i = c.length - 1; i >= 0; i--) {\n            // Case 1: Lowercase letter (part of an atom name)\n            if(c[i] >= \'a\' && c[i] <= \'z\') {\n                int end = i--;\n                // Find the start of the atom name (uppercase letter)\n                while(i >= 0 && c[i] >= \'a\' && c[i] <= \'z\') i--;\n                // Extract the full atom name\n                String key = new String(c, i, end - i + 1);\n                // Add to map, applying current frequency and multiplier\n                map.put(key, map.getOrDefault(key, 0) + Math.max(freq, 1) * multiplier);\n                freq = 0; // Reset frequency\n            } \n            // Case 2: Uppercase letter (single-letter atom)\n            else if(c[i] >= \'A\' && c[i] <= \'Z\') {\n                String key = new String(c, i, 1);\n                map.put(key, map.getOrDefault(key, 0) + Math.max(freq, 1) * multiplier);\n                freq = 0;\n            } \n            // Case 3: Number (frequency of an atom or group)\n            else if(c[i] >= \'0\' && c[i] <= \'9\') {\n                freq = c[i] - \'0\';\n                int p = 10;\n                // Parse multi-digit number\n                while(i-1 >= 0 && c[i-1] >= \'0\' && c[i-1] <= \'9\') {\n                    freq += p * (c[--i] - \'0\');\n                    p *= 10;\n                }\n            } \n            // Case 4: Closing parenthesis\n            else if(c[i] == \')\') {\n                stack[top++] = multiplier; // Save current multiplier\n                multiplier *= Math.max(freq, 1); // Update multiplier\n                freq = 0;\n            } \n            // Case 5: Opening parenthesis\n            else {\n                multiplier = stack[--top]; // Restore previous multiplier\n            }\n        }\n        \n        // Build the result string\n        StringBuilder sb = new StringBuilder();\n        for(Map.Entry<String, Integer> entry : map.entrySet()) {\n            sb.append(entry.getKey()); // Append atom name\n            if(entry.getValue() > 1) sb.append(entry.getValue()); // Append count if > 1\n        }\n        return sb.toString();\n    }\n}\n```\n```python []\nclass Solution:\n    def countOfAtoms(self, formula: str) -> str:\n        # Use collections.Counter instead of TreeMap\n        from collections import Counter\n        \n        # Function to parse a number from the formula\n        def parse_number(i):\n            if i >= len(formula) or not formula[i].isdigit():\n                return i, 1\n            num = 0\n            while i < len(formula) and formula[i].isdigit():\n                num = num * 10 + int(formula[i])\n                i += 1\n            return i, num\n\n        # Main parsing function\n        def parse():\n            nonlocal i\n            atom_count = Counter()\n            while i < len(formula):\n                if formula[i] == \'(\':\n                    i += 1\n                    inner_count = parse()\n                    i, num = parse_number(i)\n                    for atom, count in inner_count.items():\n                        atom_count[atom] += count * num\n                elif formula[i] == \')\':\n                    i += 1\n                    return atom_count\n                else:\n                    # Parse atom name\n                    j = i + 1\n                    while j < len(formula) and formula[j].islower():\n                        j += 1\n                    atom = formula[i:j]\n                    i, num = parse_number(j)\n                    atom_count[atom] += num\n            return atom_count\n\n        i = 0\n        atom_count = parse()\n\n        # Build the result string\n        return \'\'.join(atom + (str(count) if count > 1 else \'\')\n                       for atom, count in sorted(atom_count.items()))\n```\n\n# Detailed Explanation\n\n1. We start by creating a TreeMap `map` to store atom counts. TreeMap keeps its keys (atom names) sorted.\n\n2. We use an integer array `stack` as a stack to handle nested parentheses. `top` keeps track of the top of this stack.\n\n3. `multiplier` keeps track of the current multiplier for atom counts (due to parentheses).\n\n4. `freq` stores the frequency of the current atom or group.\n\n5. We convert the formula string to a character array for easier processing.\n\n6. We iterate through the formula from right to left:\n\n   a. For lowercase letters, we find the full atom name (which ends with this lowercase letter and starts with an uppercase letter). We add this atom to the map with its count.\n   \n   b. For uppercase letters, we treat it as a single-letter atom and add it to the map.\n   \n   c. For numbers, we parse the full number (which might be multi-digit) as the frequency of the preceding atom or group.\n   \n   d. For a closing parenthesis \')\', we push the current multiplier onto the stack and update the multiplier with the current frequency.\n   \n   e. For an opening parenthesis \'(\', we pop the multiplier from the stack, effectively ending the effect of this parenthesis group.\n\n7. After processing the entire formula, we build the result string:\n   - We iterate through the TreeMap entries (which are automatically sorted by atom name).\n   - For each entry, we append the atom name and its count (if the count is greater than 1).\n\n\n\n\n
['Java', 'Python3']