Watch 4 video solutions for Count Complete Substrings, a hard level problem involving Hash Table, String, Sliding Window. This walkthrough by codestorywithMIK has 9,162 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |