# Vowel Substring

📚 4 min read Tweet this post
Section titled Problem

## 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) )\$
Section titled Input%20Format%20For%20Custom%20Testing

### Input Format For Custom Testing

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

Section titled Sample%20Case%200

#### Sample Case 0

Sample Input For Custom Testing

``````STDIN         Function
-----         --------
aaeiouxa  →   s = "aaeiouxa"``````

Sample Output

`2`

Explanation

s = “aaeiouxa”

There are two qualifying substrings:

• `s[0:5] = "aaeiou"`
• `s[1:5] = "aeiou"`
Section titled Sample%20Case%201

#### Sample Case 1

Sample Input For Custom Testing

``````STDIN         Function
-----         --------
axyzaeiou →   s = "axyzaeiou"
``````

Sample Output

`1`

Explanation:

s = “axyzaeiou”

There is only one qualifying substring:

• s[4:8] = “aeiou”
Section titled Solution

## Solution

Section titled Brute%20force

### 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.
``````package main

import (
"strings"
"testing"
)

func VowelSubstring(s string) int64 {
vowels := map[byte]bool{
'a': true,
'i': true,
'u': true,
'e': true,
'o': true,
}
count := int64(0)
start := 0
n := len(s)
for start < n {
end := start
vowelTrack := "aiueo"
for end < n && vowels[s[end]] {
if !vowels[s[end]] {
break
}
vowelTrack = strings.Replace(vowelTrack, string(s[end]), "", 1)
end++
}
if len(vowelTrack) == 0 {
count++
}
start++
}

return count
}

func TestVowelSubstring(t *testing.T) {
tests := []struct {
s    string
want int64
}{
{s: "aaeiouxa", want: 2},
{s: "axyzaeiou", want: 1},
}
for _, tt := range tests {
if got := VowelSubstring(tt.s); got != tt.want {
t.Errorf("VowelSubstring(%v) = %v, want %v", tt.s, got, tt.want)
}
}
}``````

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

Section titled Time%20and%20space%20complexity

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

Section titled Optimized%20version

### 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.
``````package main

import (
"fmt"
"testing"
)

func VowelSubstring(s string) int64 {
vowels := map[byte]bool{
'a': true,
'e': true,
'i': true,
'o': true,
'u': true,
}
counts := make(map[byte]int)
start := 0
end := 0
substrings := 0
for end < len(s) {
if vowels[s[end]] {
counts[s[end]]++
} else {
start = end + 1
end = start
counts = map[byte]int{}
continue
}
fmt.Println(counts)
for len(counts) == 5 {
if len(counts) == 5 {
fmt.Println("->", len(s), " ", s, ":", s[start:end+1], start, end)
substrings++
}
if vowels[s[start]] {
counts[s[start]]--
if counts[s[start]] == 0 {
delete(counts, s[start])
}
}
start++
}
end++
}
return int64(substrings)
}

func TestVowelSubstring(t *testing.T) {
tests := []struct {
s    string
want int64
}{
{s: "aaeiouxa", want: 2},
{s: "axyzaeiou", want: 1},
{s: "aiueoaxyzaeiou", want: 3},
}
for _, tt := range tests {
if got := VowelSubstring(tt.s); got != tt.want {
t.Errorf("VowelSubstring(%v) = %v, want %v", tt.s, got, tt.want)
}
}
}``````

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

Section titled Time%20and%20space%20complexity

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

go sliding-windows