2953. Count Complete Substrings LeetCode Solution

In this guide, you will get 2953. Count Complete Substrings LeetCode Solution with the best time and space complexity. The solution to Count Complete Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Complete Substrings solution in C++
Count Complete Substrings solution in Java
Count Complete Substrings solution in Python
Additional Resources

2953. Count Complete Substrings LeetCode Solution image

Problem Statement of Count Complete Substrings

You are given a string word and an integer k.
A substring s of word is complete if:

Each character in s occurs exactly k times.
The difference between two adjacent characters is at most 2. That is, for any two adjacent characters c1 and c2 in s, the absolute difference in their positions in the alphabet is at most 2.

Return the number of complete substrings of word.
A substring is a non-empty contiguous sequence of characters in a string.

Example 1:

Input: word = “igigee”, k = 2
Output: 3
Explanation: The complete substrings where each character appears exactly twice and the difference between adjacent characters is at most 2 are: igigee, igigee, igigee.

Example 2:

Input: word = “aaabbbccc”, k = 3
Output: 6
Explanation: The complete substrings where each character appears exactly three times and the difference between adjacent characters is at most 2 are: aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc.

Constraints:

1 <= word.length <= 105
word consists only of lowercase English letters.
1 <= k <= word.length

Complexity Analysis

Time Complexity: O(26^2n)
Space Complexity: O(1)

2953. Count Complete Substrings LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

2953. Count Complete Substrings LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

2953. Count Complete Substrings LeetCode Solution in Python

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
 # code by PROGIEZ