Introduction

In this blog post, we will explore how to solve the LeetCode problem "726" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given a string formula representing a chemical formula, return the count of each atom. The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name. One or more digits representing that element's count may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, "H2O" and "H2O2" are possible, but "H1O2" is impossible. Two formulas are concatenated together to produce another formula. For example, "H2O2He3Mg4" is also a formula. A formula placed in parentheses, and a count (optionally added) is also a formula. For example, "(H2O2)" and "(H2O2)3" are formulas. Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on. The test cases are generated so that all the values in the output fit in a 32-bit integer. Example 1: Input: formula = "H2O" Output: "H2O" Explanation: The count of elements are {'H': 2, 'O': 1}. Example 2: Input: formula = "Mg(OH)2" Output: "H2MgO2" Explanation: The count of elements are {'H': 2, 'Mg': 1, 'O': 2}. Example 3: Input: formula = "K4(ON(SO3)2)2" Output: "K4N2O14S4" Explanation: The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}. Constraints: 1 <= formula.length <= 1000 formula consists of English letters, digits, '(', and ')'. formula is always valid.

Explanation

Here's the solution to the chemical formula parser and counter:

• High-Level Approach:

  • Use a stack to handle the nested parentheses. When encountering an opening parenthesis, push the current counts onto the stack. When encountering a closing parenthesis, pop the counts from the stack and multiply the counts within the parentheses by the multiplier following the closing parenthesis.
  • Iterate through the string, identifying element names and their counts. Accumulate these counts in a dictionary.
  • Sort the elements alphabetically and format the output string according to the problem's specifications.

• Complexity:

  • Runtime Complexity: O(N * log(K)), where N is the length of the formula string and K is the number of unique elements. The log(K) factor comes from sorting the element counts.
  • Storage Complexity: O(N + K), where N is the length of the formula and K is the number of unique elements. N for the stack in the worst-case nesting, and K for storing element counts.

Code

    class Solution:
    def countOfAtoms(self, formula: str) -> str:
        stack = [dict()]
        i = 0
        N = len(formula)

        while i < N:
            if formula[i] == '(':
                stack.append(dict())
                i += 1
            elif formula[i] == ')':
                i += 1
                num_start = i
                while i < N and formula[i].isdigit():
                    i += 1
                count = int(formula[num_start:i]) if num_start < i else 1

                top = stack.pop()
                for element, c in top.items():
                    stack[-1][element] = stack[-1].get(element, 0) + c * count
            else:
                start = i
                i += 1
                while i < N and formula[i].islower():
                    i += 1
                element = formula[start:i]

                num_start = i
                while i < N and formula[i].isdigit():
                    i += 1
                count = int(formula[num_start:i]) if num_start < i else 1

                stack[-1][element] = stack[-1].get(element, 0) + count

        result = ""
        counts = stack[-1]
        for element in sorted(counts.keys()):
            result += element
            if counts[element] > 1:
                result += str(counts[element])

        return result