Count Vowel Substrings of a String

EASY

Description

A substring is a contiguous (non-empty) sequence of characters within a string.

A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

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

Example 1:

Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (underlined):
- "aeiouu"
- "aeiouu"

Example 2:

Input: word = "unicornarihan"
Output: 0
Explanation: Not all 5 vowels are present, so there are no vowel substrings.

Example 3:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows (underlined):
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"

Constraints:

1 <= word.length <= 100
word consists of lowercase English letters only.

Approaches

Checkout 3 different approaches to solve Count Vowel Substrings of a String. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Enumeration

This approach involves generating every possible substring of the input word and then checking if each substring meets the criteria of a "vowel substring". A substring is valid if it contains only vowels and includes all five vowels ('a', 'e', 'i', 'o', 'u').

Algorithm

Initialize a counter count to 0.
Use two nested loops to generate all substrings. The outer loop with index i determines the start of the substring, and the inner loop with index j determines the end.
For each substring s = word.substring(i, j + 1):
Check if s is a valid vowel substring using a helper function isVowelSubstring(s).
The helper function isVowelSubstring(s) will:
- Iterate through each character of s. If any character is a consonant, return false.
- Use a HashSet to keep track of the unique vowels present in s.
- After checking all characters, if the size of the HashSet is exactly 5, return true. Otherwise, return false.
If isVowelSubstring(s) returns true, increment the count.
After checking all substrings, return count.

The algorithm iterates through all possible start and end points to define a substring. For each generated substring, it performs a two-part check. First, it verifies that every character in the substring is a vowel. If this holds, it then checks if the set of unique vowels in the substring contains all five required vowels. This is the most straightforward but also the least efficient way to solve the problem.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countVowelSubstrings(String word) {
        int count = 0;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = word.substring(i, j + 1);
                if (isVowelSubstring(sub)) {
                    count++;
                }
            }
        }
        return count;
    }

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

    private boolean isVowelSubstring(String s) {
        Set<Character> vowels = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (!isVowel(c)) {
                return false;
            }
            vowels.add(c);
        }
        return vowels.size() == 5;
    }
}

Complexity Analysis

Time Complexity: O(N^3), where N is the length of the string. The two nested loops run in O(N^2), and for each of the O(N^2) substrings, we iterate through it to check its validity, which can take up to O(N) time.Space Complexity: O(N), where N is the length of the string. This is because `word.substring(i, j + 1)` can create a new string of length up to N. The `HashSet` uses O(1) space as there are only 5 vowels.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Highly inefficient due to the cubic time complexity.
It might be too slow for larger inputs, though it passes for the given constraints (N <= 100).

Code Solutions

Checking out 3 solutions in different languages for Count Vowel Substrings of a String. Click on different languages to view the code.

class Solution {
public
  int countVowelSubstrings(String word) {
    int n = word.length();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      Set<Character> t = new HashSet<>();
      for (int j = i; j < n; ++j) {
        char c = word.charAt(j);
        if (!isVowel(c)) {
          break;
        }
        t.add(c);
        if (t.size() == 5) {
          ++ans;
        }
      }
    }
    return ans;
  }
private
  boolean isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
  }
}

Video Solution

Watch the video walkthrough for Count Vowel Substrings of a String

Data Structures:

Hash TableString

Companies:

BNY Mellon |PayPal |Snowflake |Commvault |