Count Complete Substrings

Problem Description

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 and the difference between two adjacent characters is at most 2. Return the number of complete substrings of word.

Key Insights

• A substring must have each character appearing exactly k times to be considered complete.
• Adjacent characters in the substring must have an alphabetical difference of at most 2.
• The problem can be approached using a sliding window technique combined with a hash table to count character occurrences.

Space and Time Complexity

Time Complexity: O(n^2) - In the worst case, we may need to check all possible substrings. Space Complexity: O(1) - The hash table used for character counts has a fixed size of 26 (one for each lowercase English letter).

Solution

To solve this problem, we can use a sliding window approach with two pointers. We will maintain a hash table to count occurrences of characters in the current window. The left pointer will denote the start of the substring, while the right pointer will expand the window. We'll check if the conditions for a complete substring are met as we expand the window. If they are, we will count the valid substrings. If they are not, we'll increment the left pointer to try and find a valid window again.

Code Solutions