Published on

# Vowel Substring

Authors

## Problem

Vowel Substring

Given a string of lowercase letters in the range ascii['a'-'z'], determine the number of substrings that can be created where every letter is a vowel and every vowel is present at least once. The vowels are ['a', 'e', 'i', 'o', 'u']. A substring is a contiguous group of characters in the string.

Example

s = 'aeioaexaaeuiou'

There is a substring to the left that is made of vowels, 'aeioae' which is followed by an 'x'. Since 'x' is not a vowel, it cannot be included in the substring, and this substring does not contain all of the vowels. It is not a qualifying substring. Moving to the right, there are four substrings that do qualify: 'aaeuiou', 'aaeuio', 'aeuiou' and 'aeuio'.

Constraints

1. $1 ≤ size\_of(s) ≤ 10^5$
2. $s[i] ∈ ascii['a'-'z'] (where 0 ≤ i < size\_of(s) )$

### Input Format For Custom Testing

The first line contains a string, s, that denotes the string.

#### Sample Case 0

Sample Input For Custom Testing

_3STDIN         Function_3-----         --------_3aaeiouxa →   s = "aaeiouxa"

Sample Output

2

Explanation

s = "aaeiouxa"

There are two qualifying substrings:

• s[0:5] = "aaeiou"
• s[1:5] = "aeiou"

#### Sample Case 1

Sample Input For Custom Testing

_3STDIN         Function_3-----         --------_3axyzaeiou →   s = "axyzaeiou"

Sample Output

1

Explanation:

s = "axyzaeiou"

There is only one qualifying substring:

• s[4:8] = "aeiou"

## Solution

### Brute force

Finding substring with sliding windows approach and we use 2 kind of checking:

• Check whether substring contains at least 1 from aiueo. Using map[byte]bool to track vowel already seen in substring or not. If map length equals with 5, the substring is valid.
• Check if the char is vowel or not. We can use map[byte]bool also.
_51package main_51_51import (_51 "strings"_51 "testing"_51)_51_51func VowelSubstring(s string) int64 {_51 vowels := map[byte]bool{_51 'a': true,_51 'i': true,_51 'u': true,_51 'e': true,_51 'o': true,_51 }_51 count := int64(0)_51 start := 0_51 n := len(s)_51 for start < n {_51 end := start_51 vowelTrack := "aiueo"_51 for end < n && vowels[s[end]] {_51 if !vowels[s[end]] {_51 break_51 }_51 vowelTrack = strings.Replace(vowelTrack, string(s[end]), "", 1)_51 end++_51 }_51 if len(vowelTrack) == 0 {_51 count++_51 }_51 start++_51 }_51_51 return count_51}_51_51func TestVowelSubstring(t *testing.T) {_51 tests := []struct {_51 s string_51 want int64_51 }{_51 {s: "aaeiouxa", want: 2},_51 {s: "axyzaeiou", want: 1},_51 }_51 for _, tt := range tests {_51 if got := VowelSubstring(tt.s); got != tt.want {_51 t.Errorf("VowelSubstring(%v) = %v, want %v", tt.s, got, tt.want)_51 }_51 }_51}

Try yourself https://go.dev/play/p/lyeJX_2xDqy

## Time and space complexity

The time complexity of the VowelSubstring function is O(n^2), where n is the length of the input string. This is because for each starting index of the substring, the function uses another loop to iterate over the remaining characters to find the ending index of the substring. The inner loop could potentially iterate over all remaining characters in the worst case, resulting in n iterations for each starting index, leading to a quadratic time complexity.

The space complexity of the function is O(1) because it only uses a fixed-size map vowels, a fixed-size string vowelTrack, and a few integer variables. The space used by these variables is constant and independent of the input size.

### Optimized version

How to improve time complexity the solution above to become $O(n)$ ? Utilizing sliding windows technique can improve the time complexity.

Here's how it works:

1. Initialize a map "vowels" with all the vowels as keys and their values set to true.
2. Initialize an empty map "counts" to keep track of the count of each vowel in the current substring.
3. Initialize "start" and "end" pointers to 0.
4. Initialize "substrings" variable to 0, which will keep track of the number of substrings that contain all five vowels.
5. Loop through the string until "end" pointer reaches the end of the string.
6. If the character at "end" pointer is a vowel, increment the count of that vowel in "counts" map.
7. If the character at "end" pointer is not a vowel, set the "start" pointer to the next position and move "end" pointer to the next position. Then clear counts map and continue to the next iteration.
8. If the "counts" map contains all five vowels, increment "substrings" and move the "start" pointer until the current substring no longer contains all five vowels.
9. Repeat steps 6 to 8 until "end" pointer reaches the end of the string.
10. Return the "substrings" variable, which contains the number of substrings that contain all five vowels.
main.go
_62package main_62_62import (_62 "fmt"_62 "testing"_62)_62_62func VowelSubstring(s string) int64 {_62 vowels := map[byte]bool{_62 'a': true,_62 'e': true,_62 'i': true,_62 'o': true,_62 'u': true,_62 }_62 counts := make(map[byte]int)_62 start := 0_62 end := 0_62 substrings := 0_62 for end < len(s) {_62 if vowels[s[end]] {_62 counts[s[end]]++_62 } else {_62 start = end + 1_62 end = start_62 counts = map[byte]int{}_62 continue_62 }_62 fmt.Println(counts)_62 for len(counts) == 5 {_62 if len(counts) == 5 {_62 fmt.Println("->", len(s), " ", s, ":", s[start:end+1], start, end)_62 substrings++_62 }_62 if vowels[s[start]] {_62 counts[s[start]]--_62 if counts[s[start]] == 0 {_62 delete(counts, s[start])_62 }_62 }_62 start++_62 }_62 end++_62 }_62 return int64(substrings)_62}_62_62func TestVowelSubstring(t *testing.T) {_62 tests := []struct {_62 s string_62 want int64_62 }{_62 {s: "aaeiouxa", want: 2},_62 {s: "axyzaeiou", want: 1},_62 {s: "aiueoaxyzaeiou", want: 3},_62 }_62 for _, tt := range tests {_62 if got := VowelSubstring(tt.s); got != tt.want {_62 t.Errorf("VowelSubstring(%v) = %v, want %v", tt.s, got, tt.want)_62 }_62 }_62}

Try it yourself https://go.dev/play/p/QEPERkuVdrU

### Time and space complexity

The time complexity of the solution is O(n), where n is the length of the input string. This is because we use a sliding window technique that only requires a single pass through the string, and we perform constant-time operations for each character.

The space complexity of the solution is O(1) in terms of the input size because we only use a fixed-size map vowels with 5 entries, a fixed-size map counts with at most 5 entries, and a fixed number of integer variables. The space used by the map counts and the integer variables is proportional to the number of vowels in the current window, which is at most 5. Therefore, the space complexity is constant and independent of the input size.