17 Lines, Simplest Regex Sol
TC: O(\text{regex}(n)+n+n\log n)\n## Test regexes -> https://regex101.com/\n\n# Code\npy\nclass Solution:\n    def countOfAtoms(self, s: str) -> str:\n        s
## TC: $$O(\\text{regex}(n)+n+n\\log n)$$\n## Test regexes -> https://regex101.com/\n\n# Code\n```py\nclass Solution:\n    def countOfAtoms(self, s: str) -> str:\n        s = re.sub(r\'([A-Z][a-z]*)(\\d)\', r\'(\\1)\\2\', s)  # O2 -> (O)2\n        s = re.sub(r\'(\\))(\\D|$)\', r\'\\g<1>1\\2\', s)  # (Mg)O -> (Mg)1O\n        tk = re.findall(r\'[A-Z][a-z]*|\\d+|[()]\', s)  # (MgCO3)21 -> ( Mg C O 3 ) 21\n        cf = []\n        m = 1\n        cnt = Counter()\n        for t in tk[::-1]:\n            if t == \')\': continue\n            if t == \'(\':\n                m //= cf.pop()\n                continue\n            if t.isnumeric(): \n                cf.append(int(t))\n                m *= cf[-1]\n                continue\n            cnt[t] += m\n        return \'\'.join(str(x) for p in sorted(cnt.items()) for x in p if x != 1)\n```
['Python3']