Skip to content

2953. Count Complete Substrings 👍

  • Time: $O(26^2n)$
  • Space: $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
37
38
39
40
41
42
43
44
45
class Solution {
 public:
  int countCompleteSubstrings(string word, int k) {
    const int uniqueLetters =
        unordered_set<char>{word.begin(), word.end()}.size();
    int ans = 0;

    for (int windowSize = k;
         windowSize <= k * uniqueLetters && windowSize <= word.length();
         windowSize += k)
      ans += countCompleteStrings(word, k, windowSize);

    return ans;
  }

 private:
  // Returns the number of complete substrings of `windowSize` of `word`.
  int countCompleteStrings(const string& word, int k, int windowSize) {
    int res = 0;
    int countLetters = 0;  // the number of letters in the running substring
    vector<int> count(26);

    for (int i = 0; i < word.length(); ++i) {
      ++count[word[i] - 'a'];
      ++countLetters;
      if (i > 0 && abs(word[i] - word[i - 1]) > 2) {
        count = vector<int>(26);
        // Start a new substring starting at word[i].
        ++count[word[i] - 'a'];
        countLetters = 1;
      }
      if (countLetters == windowSize + 1) {
        --count[word[i - windowSize] - 'a'];
        --countLetters;
      }
      if (countLetters == windowSize)
        res += ranges::all_of(count,
                              [k](int freq) { return freq == 0 || freq == k; })
                   ? 1
                   : 0;
    }

    return res;
  }
};

 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 {
  public int countCompleteSubstrings(String word, int k) {
    final int uniqueLetters = word.chars().boxed().collect(Collectors.toSet()).size();
    int ans = 0;

    for (int windowSize = k; windowSize <= k * uniqueLetters && windowSize <= word.length();
         windowSize += k) {
      ans += countCompleteStrings(word, k, windowSize);
    }

    return ans;
  }

  // Returns the number of complete substrings of `windowSize` of `word`.
  private int countCompleteStrings(final String word, int k, int windowSize) {
    int res = 0;
    int countLetters = 0; // the number of letters in the running substring
    int[] count = new int[26];

    for (int i = 0; i < word.length(); ++i) {
      ++count[word.charAt(i) - 'a'];
      ++countLetters;
      if (i > 0 && Math.abs(word.charAt(i) - word.charAt(i - 1)) > 2) {
        count = new int[26];
        // Start a new substring starting at word[i].
        ++count[word.charAt(i) - 'a'];
        countLetters = 1;
      }
      if (countLetters == windowSize + 1) {
        --count[word.charAt(i - windowSize) - 'a'];
        --countLetters;
      }
      if (countLetters == windowSize)
        res += Arrays.stream(count).allMatch(freq -> freq == 0 || freq == k) ? 1 : 0;
    }

    return res;
  }
}

 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 countCompleteSubstrings(self, word: str, k: int) -> int:
    uniqueLetters = len(set(word))
    return sum(self._countCompleteStrings(word, k, windowSize)
               for windowSize in range(k, k * uniqueLetters + 1, k))

  def _countCompleteStrings(self, word: str, k: int, windowSize: int) -> int:
    """
    Returns the number of complete substrings of `windowSize` of `word`.
    """
    res = 0
    countLetters = 0  # the number of letters in the running substring
    count = collections.Counter()

    for i, c in enumerate(word):
      count[c] += 1
      countLetters += 1
      if i > 0 and abs(ord(c) - ord(word[i - 1])) > 2:
        count = collections.Counter()
        # Start a new substring starting at word[i].
        count[c] += 1
        countLetters = 1
      if countLetters == windowSize + 1:
        count[word[i - windowSize]] -= 1
        countLetters -= 1
      if countLetters == windowSize:
        res += all(freq == 0 or freq == k for freq in count.values())

    return res