Introduction

In this blog post, we will explore how to solve the LeetCode problem "2063" 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 word, return the sum of the number of vowels ('a', 'e', 'i', 'o', and 'u') in every substring of word. A substring is a contiguous (non-empty) sequence of characters within a string. Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations. Example 1: Input: word = "aba" Output: 6 Explanation: All possible substrings are: "a", "ab", "aba", "b", "ba", and "a". - "b" has 0 vowels in it - "a", "ab", "ba", and "a" have 1 vowel each - "aba" has 2 vowels in it Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6. Example 2: Input: word = "abc" Output: 3 Explanation: All possible substrings are: "a", "ab", "abc", "b", "bc", and "c". - "a", "ab", and "abc" have 1 vowel each - "b", "bc", and "c" have 0 vowels each Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3. Example 3: Input: word = "ltcd" Output: 0 Explanation: There are no vowels in any substring of "ltcd". Constraints: 1 <= word.length <= 105 word consists of lowercase English letters.

Explanation

Here's an efficient solution to the problem:

• Key Idea: Instead of generating all substrings and counting vowels in each, we focus on each character in the word. For each vowel, we determine how many substrings it appears in. A vowel at index i will be part of (i + 1) substrings starting from the beginning of the word and (n - i) substrings ending at or after that index. Thus, it contributes (i + 1) * (n - i) to the total count.
• Vowel Check: Utilize a fast vowel lookup (e.g., using a set) for efficiency.

• Data Type: Use a 64-bit integer to store the result, accommodating potentially large sums due to the constraint on word length.

• Complexity:

  • Runtime: O(n), where n is the length of the word.
  • Storage: O(1) (constant extra space)

Code

    def sum_vowels(word: str) -> int:
    """
    Calculates the sum of vowels in every substring of a word.

    Args:
        word: The input string consisting of lowercase English letters.

    Returns:
        The sum of vowels in every substring of the word.
    """

    n = len(word)
    vowels = {'a', 'e', 'i', 'o', 'u'}
    total_sum = 0

    for i in range(n):
        if word[i] in vowels:
            total_sum += (i + 1) * (n - i)

    return total_sum