LeetCode 2062 - Count Vowel Substrings of a String

The problem requires counting the number of vowel substrings in a given string word. A substring is any contiguous sequence of characters within the string.

leetcodeeasyhash-tablestring

LeetCode Problem 2062

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

The problem requires counting the number of vowel substrings in a given string word. A substring is any contiguous sequence of characters within the string. A vowel substring is defined as a substring that contains only vowels ('a', 'e', 'i', 'o', 'u') and must include all five vowels at least once.

The input is a lowercase string of length between 1 and 100, so it is relatively small. The output is a single integer, representing how many substrings meet the vowel substring criteria. Important edge cases include strings with no vowels, strings shorter than 5 characters, and strings with vowels but missing one or more of the required five vowels. The problem guarantees lowercase English letters, which avoids complications with uppercase or non-alphabetic characters.

Approaches

A brute-force approach would be to generate all possible substrings of word and check each substring to see if it consists only of vowels and contains all five vowels. While correct, this approach is inefficient. Generating all substrings takes O(n²) time, and checking each substring for all five vowels can take O(n) time, giving an overall time complexity of O(n³). For n = 100, this is feasible but not optimal.

The optimal approach leverages the observation that vowel substrings are contiguous sequences of vowels. We can iterate over the string and, for every position that starts a vowel substring, expand to the right while counting the occurrences of vowels using a frequency map. Once a substring contains all five vowels, every further extension of this substring to the right also counts as a valid vowel substring. This reduces redundant checks and avoids considering substrings that include consonants.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Generate all substrings and check each one
Optimal O(n²) O(1) Expand from each vowel starting point and count vowels using a fixed-size map

Algorithm Walkthrough

  1. Define a set vowels containing 'a', 'e', 'i', 'o', 'u'. This helps quickly check if a character is a vowel.
  2. Initialize a variable count to zero to keep track of the total number of vowel substrings.
  3. Iterate through each index i in the string. If the character at i is a vowel, start considering substrings beginning at i.
  4. For each starting index i, initialize a frequency dictionary freq to track how many times each vowel appears in the current substring.
  5. Expand a pointer j from i to the end of the string. For each character at j, if it is a vowel, increment its count in freq. If it is a consonant, break the inner loop since the substring can no longer be a vowel substring.
  6. After updating freq, check if all five vowels are present (each count >= 1). If they are, increment count.
  7. Continue expanding j until a consonant is encountered or the end of the string is reached.
  8. Return count as the total number of vowel substrings.

Why it works: By expanding from each vowel starting point and stopping at the first consonant, we ensure that every substring considered consists only of vowels. The frequency map guarantees that we count only those substrings containing all five vowels. This method avoids unnecessary substring generation, reducing runtime while maintaining correctness.

Python Solution

class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        vowels = set("aeiou")
        count = 0
        n = len(word)
        
        for i in range(n):
            if word[i] not in vowels:
                continue
            freq = {}
            for j in range(i, n):
                if word[j] not in vowels:
                    break
                freq[word[j]] = freq.get(word[j], 0) + 1
                if len(freq) == 5:
                    count += 1
        return count

This Python implementation follows the optimal algorithm closely. It first checks if a character can start a vowel substring, then expands to the right while tracking vowel counts in a dictionary. Only substrings containing all five vowels increment the count. The dictionary freq ensures constant-time lookup and update for each vowel.

Go Solution

func countVowelSubstrings(word string) int {
    vowels := map[rune]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
    count := 0
    n := len(word)

    for i := 0; i < n; i++ {
        if !vowels[rune(word[i])] {
            continue
        }
        freq := map[rune]int{}
        for j := i; j < n; j++ {
            ch := rune(word[j])
            if !vowels[ch] {
                break
            }
            freq[ch]++
            if len(freq) == 5 {
                count++
            }
        }
    }
    return count
}

The Go implementation mirrors the Python solution. We use a map[rune]int to track the frequency of vowels in the current substring. Go requires explicit conversion of word[i] to rune to handle Unicode correctly, even though the input is lowercase English letters.

Worked Examples

Example 1: word = "aeiouu"

Starting at index 0, the substring "aeiou" contains all vowels. Extending to "aeiouu" also contains all vowels. Count = 2.

Example 2: word = "unicornarihan"

Iterate over all starting positions. No substring contains all five vowels. Count = 0.

Example 3: word = "cuaieuouac"

Start at index 1: "uaieu" contains all vowels. Extending the substring yields multiple valid substrings. Count = 7.

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Each starting vowel index may expand to the end, giving a nested loop over n characters.
Space O(1) The frequency map has at most 5 entries for vowels.

The quadratic time complexity is acceptable for n <= 100, and space usage is constant due to the fixed set of vowels.

Test Cases

# Provided examples
assert Solution().countVowelSubstrings("aeiouu") == 2  # multiple vowel substrings
assert Solution().countVowelSubstrings("unicornarihan") == 0  # no valid substrings
assert Solution().countVowelSubstrings("cuaieuouac") == 7  # overlapping vowel substrings

# Edge cases
assert Solution().countVowelSubstrings("a") == 0  # single vowel, cannot form all five vowels
assert Solution().countVowelSubstrings("aeiou") == 1  # exact match of all vowels
assert Solution().countVowelSubstrings("bcdfg") == 0  # no vowels at all
assert Solution().countVowelSubstrings("aeiaaioooaauuaeiou") == 15  # complex overlapping vowels
Test Why
"aeiouu" Multiple overlapping vowel substrings
"unicornarihan" No substring has all five vowels
"cuaieuouac" Overlapping vowel substrings counted multiple times
"a" Too short to contain all vowels
"aeiou" Minimal substring containing all vowels
"bcdfg" No vowels present
"aeiaaioooaauuaeiou" Tests multiple overlapping substrings with all vowels

Edge Cases

The first important edge case is strings shorter than 5 characters, which can never form a vowel substring. The implementation handles this by naturally skipping such substrings.

The second edge case involves consonants breaking vowel sequences. The algorithm correctly stops expanding the substring once a consonant is encountered.

The third edge case is overlapping substrings with all vowels, which is handled by checking all extensions of a valid starting index. Each extension that contains all five vowels is counted separately. This ensures that substrings sharing characters are still counted if they independently satisfy the vowel substring condition.