Skip to content

2062. Count Vowel Substrings of a String

  • Time: $O(n)$
  • Space: $O(26) = O(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
class Solution {
 public:
  int countVowelSubstrings(string word) {
    return countVowelSubstringsAtMost(word, 5) -
           countVowelSubstringsAtMost(word, 4);
  }

 private:
  int countVowelSubstringsAtMost(const string& s, int goal) {
    int ans = 0;
    int k = goal;
    vector<int> count(26);

    for (int l = 0, r = 0; r < s.length(); ++r) {
      if (!isVowel(s[r])) {  // Fresh start.
        l = r + 1;
        k = goal;
        count = vector<int>(26);
        continue;
      }
      if (++count[s[r] - 'a'] == 1)
        --k;
      while (k == -1)
        if (--count[s[l++] - 'a'] == 0)
          ++k;
      ans += r - l + 1;  // s[l..r], s[l + 1..r], ..., s[r]
    }

    return ans;
  }

  bool isVowel(char c) {
    static constexpr string_view kVowels = "aeiou";
    return kVowels.find(c) != string_view::npos;
  }
};

 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
class Solution {
  public int countVowelSubstrings(String word) {
    return countVowelSubstringsAtMost(word, 5) - countVowelSubstringsAtMost(word, 4);
  }

  private int countVowelSubstringsAtMost(final String s, int goal) {
    int ans = 0;
    int k = goal;
    int[] count = new int[26];

    for (int l = 0, r = 0; r < s.length(); ++r) {
      if (!isVowel(s.charAt(r))) { // Fresh start.
        l = r + 1;
        k = goal;
        count = new int[26];
        continue;
      }
      if (++count[s.charAt(r) - 'a'] == 1)
        --k;
      while (k == -1)
        if (--count[s.charAt(l++) - 'a'] == 0)
          ++k;
      ans += r - l + 1; // s[l..r], s[l + 1..r], ..., s[r]
    }

    return ans;
  }

  private boolean isVowel(char c) {
    return "aeiou".indexOf(c) != -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
class Solution:
  def countVowelSubstrings(self, word: str) -> int:
    kVowels = 'aeiou'

    def countVowelSubstringsAtMost(goal: int) -> int:
      ans = 0
      k = goal
      count = collections.Counter()

      l = 0
      for r, c in enumerate(word):
        if c not in kVowels:  # Fresh start.
          l = r + 1
          k = goal
          count = collections.Counter()
          continue
        count[c] += 1
        if count[c] == 1:
          k -= 1
        while k == -1:
          count[word[l]] -= 1
          if count[word[l]] == 0:
            k += 1
          l += 1
        ans += r - l + 1  # s[l..r], s[l + 1..r], ..., s[r]

      return ans

    return countVowelSubstringsAtMost(5) - countVowelSubstringsAtMost(4)