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".
Constraints:
1 <= word.length <= 105word consists of lowercase English letters.This approach considers all possible substrings and counts the vowels in each one. It is straightforward but computationally expensive due to its O(n^2) complexity.
This implementation checks all possible substrings of the input string word and counts the vowels in each substring.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3) due to three nested loops.
Space Complexity: O(1), no additional space needed.
For this optimized approach, consider each vowel's contribution to different substrings directly. If a character is a vowel at position i, it can appear in (i + 1) starting positions and (n - i) ending positions, totaling (i + 1) * (n - i) substrings. Sum these contributions for each vowel in the given string.
This optimized C implementation calculates the contribution of each vowel directly without generating all substrings, significantly reducing computational work.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) as we iterate through the string once.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: |
| Optimized Contribution Approach | Time Complexity: |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 views views
Watch 9 more video solutions →Practice Vowels of All Substrings with our built-in code editor and test cases.
Practice on FleetCode