algoadvance

Leetcode 2062. Count Vowel Substrings of a String

Problem Statement

Given a string word, return the number of vowel substrings in word.

A substring is a contiguous (non-empty) sequence of characters within a string. A vowel substring is a substring that contains only vowels ('a', 'e', 'i', 'o', 'u') and has all five vowels present in it.

Example:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings are "uaieuo", "aieuo", "ieuo", "euo", "uo", "ou" and "uaieuouac".

Clarifying Questions

  1. What is the maximum length of a string?
    • Assuming it fits within typical constraints for interview problems (e.g., word.length <= 10^5).
  2. Are there any special characters or is it guaranteed to be lowercase English letters only?
    • Assuming the input string consists of only lowercase English letters.

Strategy

We’ll use a sliding window technique to find all valid vowel substrings efficiently. The idea is to maintain two pointers defining a window that contains all 5 vowels and count the valid substrings within this window.

Steps:

  1. Iterate through each character in the string and identify if it is a vowel.
  2. Use two pointers to create a sliding window:
    • The first pointer left marks the start of the window.
    • The second pointer right moves to include the latest character.
  3. Maintain a frequency map of the vowels to check the presence of all five vowels within the window.
  4. Once a valid window is identified, count every valid length within the window starting from left to right.

Code

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>

bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

int countVowelSubstrings(std::string word) {
    std::unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
    int n = word.size();
    int count = 0;
    
    for(int start = 0; start < n; ++start) {
        if (vowels.find(word[start]) != vowels.end()) {
            std::unordered_set<char> seen;
            for (int end = start; end < n; ++end) {
                if (vowels.find(word[end]) != vowels.end()) {
                    seen.insert(word[end]);
                    if (seen.size() == 5) {
                        ++count;
                    }
                } else {
                    break;
                }
            }
        }
    }
    
    return count;
}

int main() {
    std::string word = "cuaieuouac";
    std::cout << "The number of vowel substrings is: " << countVowelSubstrings(word) << std::endl;
    return 0;
}

Time Complexity

The algorithm primarily involves nested loops, but it only processes a portion of the string each time a vowel is found, making it efficient.

However, the overall time complexity is (O(n^2)) in the worst case where each character processed for vowels and further processed for subsequent vowels.

This should be acceptable for n <= 10^5.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI