2062. Count Vowel Substrings of a String
Problem Description
The problem is about identifying and counting special types of substrings within a given string. A substring is any consecutive sequence of characters from a string. What makes a substring special in this problem is that it is a "vowel substring," which means two things:
- The substring consists only of vowels - which are the characters 'a', 'e', 'i', 'o', 'u'.
- The substring contains all five of these vowels at least once.
Given a string word
, the task is to return the number of such vowel substrings that exist within word
.
For example, in the string "aeiouu", there is just one vowel substring that includes all five vowels, which is "aeiou". However, if you have extra vowels after like in "aeiouua", now there are two vowel substrings - "aeiou" and "aeiouu".
Intuition
Understanding the problem, the intuitive approach is to scan through the given string and extract all possible substrings, checking each one to determine if it qualifies as a vowel substring.
Here's a simple approach:
- Create a set of vowels to use as a reference (
s
). - Iterate through all possible start positions (
i
) for a substring within the stringword
. - For each start position, iterate through all possible end positions (
j
) that create a substring. - For every start and end position, generate the substring
word[i:j]
. - Check if the set of characters in this substring matches the reference set of vowels exactly.
- If it matches, it means the substring is a vowel substring.
- Count all such instances to get the final answer.
The solution code uses a concise and elegant list comprehension combined with the sum
function to count the number of times a generated substring's set of characters matches our reference set. This keeps the implementation succinct and avoids the need for verbose loops and conditionals.
Solution Approach
The Python solution provided uses a straightforward brute-force approach coupled with some clever use of the language's built-in data structures and functions. Here's more detail on how the algorithm and data structures are used:
-
Set Data Structure: The solution starts by creating a set
s
of all vowels. Sets are chosen because they allow O(1) average time complexity for checking if an element is contained within the set, which is useful in our case when we want to quickly check if a character is a vowel. -
Iteration: The solution then iterates through all possible start and end positions for substrings within
word
. This is done using two nested loops. The outer loop (for i in range(n)
) iterates from the start of theword
string to its end. The inner loop (for j in range(i + 1, n + 1)
) iterates from the current start position to the end of the string, ensuring every possible non-empty substring is considered. -
List Comprehension and Summation: For each pair of start and end positions found in these iterations, a substring is created with
word[i:j]
. This substring is then immediately turned into a set, which removes duplicates and allows for easy comparison with the sets
of vowels. If the sets match, that means the substring contains all the vowels and only vowels, making it a valid vowel substring. The list comprehension does this for each possible substring, generating a list of true (1) and false (0) values that represent whether each substring meets the criteria. -
Counting Matches: The
sum
function then adds up the list of 1s and 0s, effectively counting the number of valid vowel substrings in the originalword
.
This process leads to a computational complexity of O(n^3), where n is the length of the string, since we have two nested loops (O(n^2)) and set creation and comparison operations that can be up to O(n). Despite the seemingly high complexity, for typical inputs that LeetCode problems expect, this solution performs adequately well.
The actual implementation in the code is concise due to the use of a one-liner list comprehension, which is a powerful feature in Python that helps to write compact and readable code.
Here is the critical part of the code explaining the implementation:
s = set('aeiou')
return sum(set(word[i:j]) == s for i in range(n) for j in range(i + 1, n + 1))
Essentially, we're checking for each substring of word
defined by [i:j]
whether the set of unique characters matches our set of vowels s
. We sum the total number of times this is True
to find our answer.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take the string "aeioouaeei"
as an example ā we'll walk through the solution approach to see how it works in finding the number of special vowel substrings.
We start by initializing a set s
with the vowels 'a'
, 'e'
, 'i'
, 'o'
, and 'u'
. As we know, the string length (n) is 10 in this case.
Now, we need to check all possible substrings and determine if they're special vowel substrings. We do this by:
- Iterating through
i
(start index of the substring) from 0 to 9. - For each
i
, we iteratej
(end index of the substring) fromi+1
to 10. - We create a substring using
word[i:j]
and convert it into a set to remove duplicates. - We then compare this set to our initial vowels set
s
. - If the sets are equal, we've found a special vowel substring.
Let's walk through the first few iterations:
- Iteration 1:
i = 0
,j = 5
, substring is"aeioo"
which yields a set of{'a', 'e', 'i', 'o'}
. This does not matchs
, so we don't count it. - Iteration 2:
i = 0
,j = 6
, substring is"aeioou"
which yields a set of{'a', 'e', 'i', 'o', 'u'}
. This matchess
, so we count one occurrence. - ...
- We continue this process, checking all the possible substrings.
After we finish iterating over all the start and end indices, we sum up the true instances where the condition was met, and this gives us the number of special vowel substrings within the word. For "aeioouaeei"
, the valid substrings include "aeioou"
, "aeiooua"
, "aeioouae"
, "aeioouaee"
, and "aeioouaeei"
- each containing all vowels at least once.
Using the provided code snippet with our example string:
s = set('aeiou')
n = len("aeioouaeei")
return sum(set(word[i:j]) == s for i in range(n) for j in range(i + 1, n + 1))
The code will check all substrings and find that there are 5 substrings that match the criteria, returning 5
as the output. This approach, albeit brute force and suboptimal for very large strings, works efficiently for the input sizes usually encountered on LeetCode.
Solution Implementation
1class Solution:
2 def countVowelSubstrings(self, word: str) -> int:
3 # Length of the input word
4 length = len(word)
5
6 # Set containing all vowels for comparison
7 vowels_set = {'a', 'e', 'i', 'o', 'u'}
8
9 # Using list comprehension and sum to count all substrings
10 # that contain exactly the vowels 'a', 'e', 'i', 'o', 'u'
11 # For every possible substring defined by indices i and j,
12 # we check if the set of characters in that substring matches
13 # the set of vowels. We sum up all such occurrences.
14 return sum(set(word[i:j]) == vowels_set for i in range(length) for j in range(i + 1, length + 1))
15
1class Solution {
2 // Method to count the number of vowel substrings with all 5 English vowels
3 public int countVowelSubstrings(String word) {
4 int stringLength = word.length(); // Get the length of the word
5 int count = 0; // Initialize the count of substrings
6
7 // Iterate over each character in the word
8 for (int i = 0; i < stringLength; ++i) {
9 // Create a set to store unique vowels of the current substring
10 Set<Character> uniqueVowels = new HashSet<>();
11
12 // Start from the current character and check subsequent characters
13 for (int j = i; j < stringLength; ++j) {
14 char currentChar = word.charAt(j); // Get the current character
15 // If the character is not a vowel, break the inner loop
16 if (!isVowel(currentChar)) {
17 break;
18 }
19 // Add the vowel to the set of unique vowels
20 uniqueVowels.add(currentChar);
21 // If the set contains all 5 unique vowels, increment the count
22 if (uniqueVowels.size() == 5) {
23 count++;
24 }
25 }
26 }
27 return count; // Return the total count of vowel substrings
28 }
29
30 // Helper method to determine whether a character is a vowel
31 private boolean isVowel(char character) {
32 // Compare the character to all vowels and return true if it matches any
33 return character == 'a' || character == 'e' || character == 'i' || character == 'o' || character == 'u';
34 }
35}
36
1#include <unordered_set>
2#include <string>
3
4class Solution {
5public:
6 // Counts the number of substrings that contain all vowel characters (aeiou) at least once
7 int countVowelSubstrings(string word) {
8 int count = 0; // Initialize the count of vowel-only substrings
9 int wordSize = word.size(); // Store the size of the word for the loop condition
10
11 // Iterate through each character of the string as a starting point
12 for (int start = 0; start < wordSize; ++start) {
13 std::unordered_set<char> vowels; // Initialize a set to keep track of vowels in the current substring
14
15 // Extend the current substring by considering each subsequent character
16 for (int end = start; end < wordSize; ++end) {
17 char currentChar = word[end];
18
19 // If the current character is not a vowel, break out of the inner loop
20 if (!isVowel(currentChar)) break;
21
22 // Add the current vowel to the set
23 vowels.insert(currentChar);
24
25 // If we have encountered all 5 vowels, increment the count
26 count += vowels.size() == 5;
27 }
28 }
29
30 return count; // Return the total count of vowel-only substrings
31 }
32
33 // Helper function to determine if a character is a vowel
34 bool isVowel(char c) {
35 return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
36 }
37};
38
39// Example usage:
40// Solution solution;
41// int result = solution.countVowelSubstrings("aaeiuo"); // This would return the count of valid substrings
42
1// Function to count vowel beauty substrings in a given word.
2function countVowelSubstrings(word: string): number {
3 let count = 0; // Initialize counter for beautiful substrings
4 const length = word.length; // Store length of the word
5
6 // Iterate through each character of the word
7 for (let i = 0; i < length; ++i) {
8 const vowels = new Set<string>(); // A set to store unique vowels encountered
9
10 // Explore every substring starting at position 'i'
11 for (let j = i; j < length; ++j) {
12 const character = word[j]; // The current character
13
14 // Check if character is a vowel
15 if (character === 'a' || character === 'e' || character === 'i' || character === 'o' || character === 'u') {
16 vowels.add(character); // Add the vowel to the set
17
18 // Check if all 5 vowels have been encountered
19 if (vowels.size === 5) {
20 count++; // Increment counter as all vowels are present
21 }
22 } else {
23 // If it's not a vowel, break the loop as the current substring cannot be beautiful.
24 break;
25 }
26 }
27 }
28
29 return count; // Return the total number of beautiful substrings found.
30}
31
Time and Space Complexity
The time complexity of the provided code is O(n^3)
. This is because the code uses two nested loops iterating over the length of the word, resulting in n^2
iterations, and within each iteration, it creates a substring and converts it to a set. The creation of a set from the substring takes O(k)
, where k
is the length of the substring, which averages to n/2
over all possible substrings. This gives us a total of O(n^2 * n/2)
, which simplifies to O(n^3)
.
The space complexity is O(n)
, primarily because of the storage required for the set of vowels s
and the substring set in each iteration. The size of set s
is constant (with 5 vowels), but the space used for the substring can grow up to the size of the input word in the worst case, hence the space complexity O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!