[LeetCode] 2062. Count Vowel Substrings of a String

轉自LeetCode

A substring is a contiguous (non-empty) sequence of characters within a string.

A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', and 'u') and has all five vowels present in it.

Given a string word, return the number of vowel substrings in word.

 

Example 1:

Input: word = "aeiouu"
Output: 2
Explanation: The vowel substrings of word are as follows (underlined):
- "aeiouu"
- "aeiouu"

Example 2:

Input: word = "unicornarihan"
Output: 0
Explanation: Not all 5 vowels are present, so there are no vowel substrings.

Example 3:

Input: word = "cuaieuouac"
Output: 7
Explanation: The vowel substrings of word are as follows (underlined):
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"
- "cuaieuouac"

Example 4:

Input: word = "bbaeixoubb"
Output: 0
Explanation: The only substrings that contain all five vowels also contain consonants, so there are no vowel substrings.

 

Constraints:

• 1 <= word.length <= 100
• word consists of lowercase English letters only.

Solution

這題被標做 easy 感覺不太對，應該至少是 medium 等級

想法還是用 sliding window 來解，但需要變形一下

首先，map 裡面就五個key (a,e,i,o,u)，其初始值都是 0

當歷遍 word 的時候，如果不是這五個char，把所有值都初始化，並把對應的指標移動

因為之後都必須重新算

而如果遇到這五個 char，那麼就要開始在這個 window 裡面做計算

右邊界(right)就是一直往右走，並按上面的規則走

左邊界(left)也是按照上面規則走，當遇到不是 vowel 的字元時才會移動

當全部的vowel 都被使用了，這時候就可以來計算

而 substringLeft 就是這次個關鍵，拿來計算可以有多少 substring 用

用個例子來舉例:  t s a a e i o u r

將 substringLeft 往右移，一直到某個 vowel 沒有使用到了

在這個例子就是 a 這個 char 沒有用到了

那這時候就可以看成 "eiou" 後面這個 string 可以搭配前面的一個 a 或是前面的兩個 aa

來形成符合題意的 substring -> "aeiou" and "aaeiou"

所以這時候的計數就是 substringLeft - left

kotlin(參考解法)

	class Solution {
	fun countVowelSubstrings(word: String): Int {
	val map = mutableMapOf<Char,Int>()
	map['a'] = 0
	map['e'] = 0
	map['i'] = 0
	map['o'] = 0
	map['u'] = 0
	var ans = 0
	var count = 0
	var left = 0
	var substringLeft = 0
	for(right in word.indices) {
	if (map[word[right]] == null) {
	map['a'] = 0
	map['e'] = 0
	map['i'] = 0
	map['o'] = 0
	map['u'] = 0
	count = 0
	left = right + 1 // move to the next position
	substringLeft = right + 1 // move to the next position
	} else {
	map[word[right]] = map[word[right]]!! + 1
	//ignore duplicated vowel
	if(map[word[right]] == 1) {
	++count
	}
	while(count == 5) {
	map[word[substringLeft]] = map[word[substringLeft]]!! - 1
	if(map[word[substringLeft]] == 0) {
	--count
	}
	++substringLeft
	}
	ans += substringLeft - left
	}
	}
	return ans
	}
	}

view raw count_vowel_substrings_of_a_string.kt hosted with ❤ by GitHub