algoadvance

Leetcode 2062. Count Vowel Substrings of a String

Problem Statement

You are given a string word. A vowel substring is a substring of word that consists only of vowels (a, e, i, o, u) and has all five vowels present at least once.

Your task is to return the number of vowel substrings in the given word.

Example

  1. Input: word = "aeiouu" Output: 2

  2. Input: word = "unicornarihan" Output: 0

  3. Input: word = "cuaieuouac" Output: 7

Constraints

Clarifying Questions

  1. Should the vowels be contiguous in the substring?
    • Yes, the vowels should form a contiguous substring.
  2. Is y considered a vowel in this context?
    • No, only a, e, i, o, u are considered vowels.
  3. Do we need to count overlapping substrings?
    • Yes, overlapping substrings should be counted.

Strategy

To solve this problem, we can use a sliding window approach:

  1. Identify Vowel Substrings: Iterate over the string and use two pointers to identify substrings that contain only vowels.
  2. Check for All Vowels Presence: For each identified substring, check if it contains all five vowels.
  3. Count Valid Substrings: Increment the count whenever a valid substring is found.

We will accomplish this in a nested loop to check all substrings and use a set to check the presence of vowels.

Code

import java.util.*;

public class Solution {
    public int countVowelSubstrings(String word) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
        int count = 0;
        
        for (int i = 0; i < word.length(); i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < word.length(); j++) {
                char ch = word.charAt(j);
                if (!vowels.contains(ch)) {
                    break;
                }
                seen.add(ch);
                if (seen.size() == 5) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

Time Complexity

The time complexity of this solution is O(n^2), where n is the length of the input string:

The space complexity is O(1) since we are using a fixed size set to keep track of vowels seen in the current substring.

Analysis

This algorithm effectively checks each possible substring in a nested manner and ensures that all conditions for a valid vowel substring are met. The constraints (word length up to 100) make the O(n^2) approach feasible.

This concludes the solution to the “Count Vowel Substrings of a String” problem.

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