2062. Count Vowel Substrings of a String

Posted on In Views: 28 Words count: 2.2k Reading time ≈ 2 mins.

2062. Count Vowel Substrings of a String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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.

难度 : Easy

思路

Sliding Window
使用HashMap存放当前window里的 a,e,i,o,u每个字符的个数
l表示window 开始的位置，k 表示满足条件最小的位置，r表示window结束的位置
那么[l,r]里满足条件的window的个数就是 k-l
当遇到了位置 i 是非vowels的字符，hashmap里的个数清零，window的起始位置为i+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int countVowelSubstrings(String word) {
        Map<Character,Integer> map = new HashMap<>();
        reset(map);        
        int l = 0;        
        int k = 0;
        int vowels = 0;
        int ans = 0;
        for(int r = 0; r < word.length(); r++) {
            char c = word.charAt(r);
            if (map.containsKey(c)) {
                int cnt = map.get(c) + 1;
                map.put(c, cnt);
                if (cnt == 1) {
                    vowels++;    
                }
                //find the min window, the position of k
                for (;vowels == 5; k++) {
                    //start to move k
                    int kCnt = map.get(word.charAt(k)) - 1;
                    map.put(word.charAt(k), kCnt);
                    //kCnt == 0 means the window only has 4 vowels now
                    vowels -= (kCnt == 0 ? 1 : 0);
                }
                ans += (k - l);
            } else {
                reset(map);
                l = k = r + 1;
                vowels = 0;
            }
        }
        return ans;
    }
    private void reset(Map<Character,Integer> map) {
        map.put('a',0);
        map.put('e',0);
        map.put('i',0);
        map.put('o',0);
        map.put('u',0);
    }
}