C# Solution for Number of Atoms Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to parse a chemical formula string, count the occurrences of each atom, and
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to parse a chemical formula string, count the occurrences of each atom, and return the counts in a specific sorted format. The formula can include nested parentheses, which introduce multiplicative factors for the atoms inside them. Handling these nested structures correctly is the main challenge.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tUse a Stack for Nested Parentheses:\n\t\u2022\tUse a stack to manage the nested structure of the formula. When encountering an opening parenthesis (, push the current count map onto the stack and start a new map. When encountering a closing parenthesis ), pop the map from the stack, multiply its counts by the following multiplicity, and merge it back into the current map.\n2.\tParse Elements and Counts:\n\t\u2022\tTraverse the string to parse elements, which start with an uppercase letter and may be followed by lowercase letters.\n\t\u2022\tParse the count of the element, which follows the element and may be a multi-digit number. If no count is specified, it defaults to 1.\n3.\tMerge Counts:\n\t\u2022\tWhen merging counts from nested maps, ensure that the counts are correctly multiplied by the specified multiplicity before adding them to the current map.\n4.\tSort and Format the Result:\n\t\u2022\tUse a SortedDictionary to automatically sort the elements by their names.\n\t\u2022\tConstruct the result string based on the sorted elements and their counts.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\u2022\tParsing the String: Each character in the formula is processed at most once, resulting in O(n) time complexity, where n is the length of the formula.\n\u2022\tMerging Maps: In the worst case, each element within nested parentheses needs to be processed. The merging process is efficient due to the use of a stack, so the overall complexity remains linear relative to the number of characters.\n\u2022\tSorting the Elements: Sorting the elements using a SortedDictionary takes O(m log m) time, where m is the number of unique elements.\n\nThus, the overall time complexity is O(n + m log m).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\u2022\tStack: The stack depth corresponds to the maximum nesting level of parentheses, which can be up to O(n) in the worst case.\n\u2022\tMaps: We maintain maps for counting elements, and the space required for the maps is proportional to the number of unique elements, O(m).\n\u2022\tSortedDictionary: The space for the SortedDictionary is also O(m) due to storing unique elements and their counts.\n\nThus, the overall space complexity is O(n + m).\n\n# Code\n```\npublic class Solution {\n    public string CountOfAtoms(string formula) {\n        int n = formula.Length;\n        Stack<Dictionary<string, int>> stack = new Stack<Dictionary<string, int>>();\n        Dictionary<string, int> map = new Dictionary<string, int>();\n        int i = 0;\n        \n        while (i < n) {\n            char ch = formula[i];\n            \n            if (ch == \'(\') {\n                // Push current map to stack and start a new map\n                stack.Push(map);\n                map = new Dictionary<string, int>();\n                i++;\n            } else if (ch == \')\') {\n                // Pop map from stack and merge with current map\n                i++;\n                int start = i;\n                int multiplicity = 1;\n                if (i < n && Char.IsDigit(formula[i])) {\n                    while (i < n && Char.IsDigit(formula[i])) i++;\n                    multiplicity = int.Parse(formula.Substring(start, i - start));\n                }\n                \n                if (stack.Count > 0) {\n                    Dictionary<string, int> tempMap = map;\n                    map = stack.Pop();\n                    foreach (var key in tempMap.Keys) {\n                        if (map.ContainsKey(key)) {\n                            map[key] += tempMap[key] * multiplicity;\n                        } else {\n                            map[key] = tempMap[key] * multiplicity;\n                        }\n                    }\n                }\n            } else {\n                int start = i;\n                i++;\n                while (i < n && Char.IsLower(formula[i])) i++;\n                string element = formula.Substring(start, i - start);\n                start = i;\n                while (i < n && Char.IsDigit(formula[i])) i++;\n                int count = start < i ? int.Parse(formula.Substring(start, i - start)) : 1;\n                if (map.ContainsKey(element)) {\n                    map[element] += count;\n                } else {\n                    map[element] = count;\n                }\n            }\n        }\n        \n        // Sort the elements and build the final string\n        SortedDictionary<string, int> sortedMap = new SortedDictionary<string, int>(map);\n        StringBuilder result = new StringBuilder();\n        foreach (var entry in sortedMap) {\n            result.Append(entry.Key);\n            if (entry.Value > 1) {\n                result.Append(entry.Value);\n            }\n        }\n        \n        return result.ToString();\n    }\n}\n```
['C#']