Vowel Substring

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 ≤ size\_of(s) ≤ 10^5$
$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

STDIN         Function
-----         --------
aaeiouxa  →   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

STDIN         Function
-----         --------
axyzaeiou →   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.

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

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:

Initialize a map "vowels" with all the vowels as keys and their values set to true.
Initialize an empty map "counts" to keep track of the count of each vowel in the current substring.
Initialize "start" and "end" pointers to 0.
Initialize "substrings" variable to 0, which will keep track of the number of substrings that contain all five vowels.
Loop through the string until "end" pointer reaches the end of the string.
If the character at "end" pointer is a vowel, increment the count of that vowel in "counts" map.
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.
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.
Repeat steps 6 to 8 until "end" pointer reaches the end of the string.
Return the "substrings" variable, which contains the number of substrings that contain all five vowels.

main.go

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

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.