Skip to content

3305. Count of Substrings Containing Every Vowel and K Consonants I 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
44
45
46
47
48
49
50
51
class Solution {
 public:
  int countOfSubstrings(string word, int k) {
    return substringsWithAtMost(word, k) - substringsWithAtMost(word, k - 1);
  }

 private:
  // Return the number of substrings containing every vowel with at most k
  // consonants.
  int substringsWithAtMost(const string& word, int k) {
    if (k == -1)
      return 0;

    int res = 0;
    int vowels = 0;
    int uniqueVowels = 0;
    unordered_map<char, int> vowelLastSeen;

    for (int l = 0, r = 0; r < word.length(); ++r) {
      if (isVowel(word[r])) {
        ++vowels;
        if (const auto it = vowelLastSeen.find(word[r]);
            it == vowelLastSeen.end() || it->second < l)
          ++uniqueVowels;
        vowelLastSeen[word[r]] = r;
      }
      while (r - l + 1 - vowels > k) {
        if (isVowel(word[l])) {
          --vowels;
          if (vowelLastSeen[word[l]] == l)
            --uniqueVowels;
        }
        ++l;
      }
      if (uniqueVowels == 5)
        // Add substrings containing every vowel with at most k consonants to
        // the answer. They are
        // word[l..r], word[l + 1..r], ..., word[min(vowelLastSeen[vowel])..r]
        res += min({vowelLastSeen['a'], vowelLastSeen['e'], vowelLastSeen['i'],
                    vowelLastSeen['o'], vowelLastSeen['u']}) -
               l + 1;
    }

    return res;
  }

  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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
  public int countOfSubstrings(String word, int k) {
    return substringsWithAtMost(word, k) - substringsWithAtMost(word, k - 1);
  }

  // Return the number of substrings containing every vowel with at most k
  // consonants.
  private int substringsWithAtMost(String word, int k) {
    if (k == -1)
      return 0;

    int res = 0;
    int vowels = 0;
    int uniqueVowels = 0;
    Map<Character, Integer> vowelLastSeen = new HashMap<>();

    for (int l = 0, r = 0; r < word.length(); ++r) {
      if (isVowel(word.charAt(r))) {
        ++vowels;
        if (!vowelLastSeen.containsKey(word.charAt(r)) || vowelLastSeen.get(word.charAt(r)) < l)
          ++uniqueVowels;
        vowelLastSeen.put(word.charAt(r), r);
      }
      while (r - l + 1 - vowels > k) {
        if (isVowel(word.charAt(l))) {
          --vowels;
          if (vowelLastSeen.get(word.charAt(l)) == l)
            --uniqueVowels;
        }
        ++l;
      }
      if (uniqueVowels == 5) {
        // Add substrings containing every vowel with at most k consonants to
        // the answer. They are
        // word[l..r], word[l + 1..r], ..., word[min(vowelLastSeen[vowel])..r]
        final int minVowelLastSeen = Arrays.asList('a', 'e', 'i', 'o', 'u')
                                         .stream()
                                         .mapToInt(vowel -> vowelLastSeen.get(vowel))
                                         .min()
                                         .getAsInt();
        res += minVowelLastSeen - l + 1;
      }
    }

    return res;
  }

  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
30
31
32
33
34
35
36
37
38
39
class Solution:
  def countOfSubstrings(self, word: str, k: int) -> int:
    VOWELS = 'aeiou'

    def substringsWithAtMost(k: int) -> int:
      """
      Return the number of substrings containing every vowel with at most k
      consonants.
      """
      if k == -1:
        return 0

      res = 0
      vowels = 0
      uniqueVowels = 0
      vowelLastSeen = {}

      l = 0
      for r, c in enumerate(word):
        if c in VOWELS:
          vowels += 1
          if c not in vowelLastSeen or vowelLastSeen[c] < l:
            uniqueVowels += 1
          vowelLastSeen[c] = r
        while r - l + 1 - vowels > k:
          if word[l] in VOWELS:
            vowels -= 1
            if vowelLastSeen[word[l]] == l:
              uniqueVowels -= 1
          l += 1
        if uniqueVowels == 5:
          # Add substrings containing every vowel with at most k consonants to
          # the answer. They are
          # word[l..r], word[l + 1..r], ..., word[min(vowelLastSeen[vowel])..r]
          res += min(vowelLastSeen[vowel] for vowel in VOWELS) - l + 1

      return res

    return substringsWithAtMost(k) - substringsWithAtMost(k - 1)