In this guide, you will get 2063. Vowels of All Substrings LeetCode Solution with the best time and space complexity. The solution to Vowels of All Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given a string word, return the sum of the number of vowels (‘a’, ‘e’, ‘i’, ‘o’, and ‘u’) in every substring of word.
A substring is a contiguous (non-empty) sequence of characters within a string.
Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.
Example 1:
Input: word = “aba”
Output: 6
Explanation:
All possible substrings are: “a”, “ab”, “aba”, “b”, “ba”, and “a”.
– “b” has 0 vowels in it
– “a”, “ab”, “ba”, and “a” have 1 vowel each
– “aba” has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6.
Example 2:
Input: word = “abc”
Output: 3
Explanation:
All possible substrings are: “a”, “ab”, “abc”, “b”, “bc”, and “c”.
– “a”, “ab”, and “abc” have 1 vowel each
– “b”, “bc”, and “c” have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.
Example 3:
Input: word = “ltcd”
Output: 0
Explanation: There are no vowels in any substring of “ltcd”.
1 <= word.length <= 105
word consists of lowercase English letters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2063. Vowels of All Substrings LeetCode Solution in C++
class Solution {
public:
long long countVowels(string word) {
// dp[i] := the sum of the number of vowels of word[0..i), ...,
// word[i - 1..i)
vector<long> dp(word.length() + 1);
for (int i = 1; i <= word.length(); ++i) {
dp[i] = dp[i - 1];
if (isVowel(word[i - 1]))
dp[i] += i;
}
return accumulate(dp.begin(), dp.end(), 0L);
}
private:
bool isVowel(char c) {
static constexpr string_view kVowels = "aeiou";
return kVowels.find(c) != string_view::npos;
}
}; /* code provided by PROGIEZ */
2063. Vowels of All Substrings LeetCode Solution in Java
class Solution {
public long countVowels(String word) {
// dp[i] := the sum of the number of vowels of word[0..i), ...,
// word[i - 1..i)
long[] dp = new long[word.length() + 1];
for (int i = 1; i <= word.length(); ++i) {
dp[i] = dp[i - 1];
if (isVowel(word.charAt(i - 1)))
dp[i] += i;
}
return Arrays.stream(dp).sum();
}
private boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
} // code provided by PROGIEZ
2063. Vowels of All Substrings LeetCode Solution in Python
class Solution:
def countVowels(self, word: str) -> int:
# dp[i] := the sum of the number of vowels of word[0..i), ...,
# word[i - 1..i)
dp = [0] * (len(word) + 1)
for i, c in enumerate(word):
dp[i + 1] = dp[i]
if c in 'aeiou':
dp[i + 1] += i + 1
return sum(dp) # code by PROGIEZ
