Scale Engineer

Count Vowel Substrings of a String

Easy
#1878Time: 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: 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.4 companies
Data structures
Hash TableString
Companies
BNY MellonPayPalSnowflakeCommvault

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem