You are given a string word and an integer k.
A substring s of word is complete if:
s occurs exactly k times.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 <= 105word consists only of lowercase English letters.1 <= k <= word.lengthProblem Overview: Given a string word and an integer k, count substrings where every distinct character appears exactly k times and the absolute difference between adjacent characters is at most 2. The substring must satisfy both constraints simultaneously, which means you must carefully control character frequency while maintaining a valid character range.
Approach 1: Brute Force Substring Validation (O(n2 * 26) time, O(26) space)
Generate every possible substring starting at index i and expand it to the right. Maintain a frequency map for characters as the substring grows. At each step, verify two conditions: the difference between the current and previous character is ≤ 2, and every character in the substring appears exactly k times. Because a substring can contain at most 26 lowercase letters, validating frequencies takes constant time. This approach works for small inputs and is useful to confirm correctness, but scanning all substrings leads to quadratic growth.
Approach 2: Sliding Window with Frequency Map (O(26 * n) time, O(26) space)
The key observation: if every character appears exactly k times, the substring length must be distinct * k. Iterate over possible numbers of distinct characters from 1 to 26. For each target count, use a fixed-length sliding window of size distinct * k. Track character frequencies using a hash map or fixed array and maintain a counter of characters whose frequency equals k. When the window size matches distinct * k and all tracked characters have frequency k, the substring is complete.
The adjacency constraint (|word[i] - word[i-1]| ≤ 2) breaks the string into independent segments. If two neighboring characters differ by more than 2, no valid substring can cross that boundary. Split the string into such segments and run the sliding window logic inside each segment separately. This significantly reduces unnecessary checks.
This technique combines sliding window mechanics with a small hash table (or frequency array) to maintain counts efficiently while iterating through the string. Each index participates in a limited number of window adjustments, giving near-linear performance.
Recommended for interviews: Interviewers expect the sliding window solution. The brute force approach demonstrates that you understand the definition of a complete substring, but the optimized window with frequency tracking shows strong algorithmic thinking and familiarity with substring counting patterns.
Using a sliding window technique can help efficiently find substrings that meet the conditions. By utilizing a frequency map, keep track of character occurrences within the current window, and ensure that each character meets the exact frequency required. This helps quickly validate if the window is a potential 'complete' substring.
To handle the adjacency requirement, ensure that the absolute difference between any two adjacent character's ASCII values meets the condition within the same window.
This Python function leverages a sliding window approach with an integer array 'frequency' to count character occurrences. The 'start' pointer is adjusted whenever the conditions are violated, either by excess character frequency or window size exceeding possible options, and counts valid windows.
The time complexity of this function is O(n), where n is the length of the string. The space complexity is O(1), since the frequency array size is constant at 26.
This approach involves generating all possible substrings of 'word' and checking each substring for the character frequency and adjacency conditions. Though less efficient than the sliding window method, this is easier to implement and understand.
This Java solution uses a brute-force methodology to inspect each substring for potential completeness. The 'isValid' helper function ensures that each substring meets the frequency and adjacency rules.
The time complexity is O(n^3) due to the need for checking each possible substring. The space complexity is O(1) apart from the input as a constant array is used.
According to condition 2 in the problem description, we can find that in a complete string, the difference between two adjacent characters does not exceed 2. Therefore, we traverse the string word, and we can use two pointers to split word into several substrings. The number of character types in these substrings does not exceed 26, and the difference between adjacent characters does not exceed 2. Next, we only need to count the number of substrings in each substring where each character appears k times.
We define a function f(s), which is used to count the number of substrings in the string s where each character appears k times. Since the number of character types in s does not exceed 26, we can enumerate each character type i, where 1 \le i \le 26, then the length of the substring with character type i is l = i times k.
We can use an array or hash table cnt to maintain the number of times each character appears in a sliding window of length l, and use another hash table freq to maintain the number of times each frequency appears. If freq[k] = i, that is, there are i characters that appear k times, then we have found a substring that meets the conditions. We can use two pointers to maintain this sliding window. Each time we move the right pointer, we increase the number of times the character pointed to by the right pointer appears and update the freq array; each time we move the left pointer, we decrease the number of times the character pointed to by the left pointer appears and update the freq array. After each pointer movement, we judge whether freq[k] is equal to i. If it is equal, it means that we have found a substring that meets the conditions.
The time complexity is O(n times |\Sigma|), and the space complexity is O(|\Sigma|), where n is the length of the string word; and \Sigma is the size of the character set. In this problem, the character set is lowercase English letters, so |\Sigma| = 26.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window with Frequency Map | The time complexity of this function is O(n), where n is the length of the string. The space complexity is O(1), since the frequency array size is constant at 26. |
| Brute Force Substring Validation | The time complexity is O(n^3) due to the need for checking each possible substring. The space complexity is O(1) apart from the input as a constant array is used. |
| Enumerate Character Types + Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Validation | O(n² * 26) | O(26) | Useful for understanding the definition of a complete substring or validating small inputs |
| Sliding Window with Frequency Map | O(26 * n) | O(26) | General case and interview solution; efficiently counts valid substrings using fixed window sizes |
Count Complete Substrings | Sliding Window | Weekly Contest 374 | Leetcode-2953 • codestorywithMIK • 9,162 views views
Watch 3 more video solutions →Practice Count Complete Substrings with our built-in code editor and test cases.
Practice on FleetCode