Count Complete Substrings

Hard

#2633Time: O(N^3) - There are O(N^2) substrings. For each substring of average length O(N), we perform a check that takes O(N) time. This results in a total time complexity of O(N^3).Space: O(1) - The space used for the frequency map is constant (size 26).

Patterns

Sliding Window

Data structures

Hash Table String

Prompt

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 <= 10⁵
word consists only of lowercase English letters.
1 <= k <= word.length

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to check every single substring of the given word. We can generate all substrings and, for each one, verify if it meets the two conditions for being 'complete': the adjacency character difference and the exact frequency count.

Algorithm

Initialize a counter for complete substrings to zero.
Generate all possible substrings of the input word using two nested loops. The outer loop iterates through the starting index i, and the inner loop iterates through the ending index j.
For each substring s = word.substring(i, j + 1): a. Check Adjacency Condition: Iterate from the first to the second-to-last character of s. If abs(s.charAt(p) - s.charAt(p + 1)) > 2 for any p, the substring is not complete. Continue to the next substring. b. Check Frequency Condition: If the adjacency condition holds, create a frequency map (e.g., an array of size 26) for the characters in s. c. Iterate through the frequency map. If any character has a frequency that is non-zero but not equal to k, the substring is not complete. d. If both conditions are satisfied, increment the counter.
Return the final count.

Walkthrough

This method involves three nested loops. The first two loops define the boundaries of a substring. The third loop (or loops) is used to validate the substring against the problem's conditions. While simple to conceptualize, its performance is very poor for large inputs.

1class Solution {2    public int countCompleteSubstrings(String word, int k) {3        int n = word.length();4        int count = 0;5        for (int i = 0; i < n; i++) {6            for (int j = i; j < n; j++) {7                String sub = word.substring(i, j + 1);8                if (isComplete(sub, k)) {9                    count++;10                }11            }12        }13        return count;14    }15 16    private boolean isComplete(String s, int k) {17        // Check adjacency condition18        for (int i = 0; i < s.length() - 1; i++) {19            if (Math.abs(s.charAt(i) - s.charAt(i + 1)) > 2) {20                return false;21            }22        }23 24        // Check frequency condition25        int[] freq = new int[26];26        for (char c : s.toCharArray()) {27            freq[c - 'a']++;28        }29 30        for (int f : freq) {31            if (f > 0 && f != k) {32                return false;33            }34        }35        return true;36    }37}

Complexity

Time

O(N^3) - There are O(N^2) substrings. For each substring of average length O(N), we perform a check that takes O(N) time. This results in a total time complexity of O(N^3).

Space

O(1) - The space used for the frequency map is constant (size 26).

Trade-offs

Pros

Simple to understand and implement.
Correct for small input sizes.

Cons

Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints (N up to 10^5).

A significant optimization comes from realizing that the adjacency condition (abs(c1 - c2) <= 2) allows us to partition the problem. We can split the word into chunks where this condition holds for all adjacent characters. Then, we only need to search for complete substrings within these chunks. For each chunk, we can use a more optimized O(M^2) approach (where M is the chunk length) instead of O(M^3).

Algorithm

Split into Chunks: First, iterate through the word and split it into smaller chunks wherever two adjacent characters word[i] and word[i+1] have a difference abs(word[i] - word[i+1]) > 2. Any complete substring must be entirely contained within one of these chunks.
Process Each Chunk: For each chunk, find the number of complete substrings and add it to a total count.
Find Substrings in a Chunk: To find complete substrings within a chunk s: a. Iterate through each possible starting index i of s. b. For each i, start a new sliding window. Use a second pointer j to expand the window to the right, from i to the end of the chunk. c. Maintain a frequency map for the characters in the current window s[i...j]. d. As j advances, update the frequency map. If any character's count exceeds k, this window and any further extensions from i are invalid, so we can break the inner loop over j. e. At each step j, check if the substring is complete. A key observation is that if no character count exceeds k, the substring is complete if and only if (number of distinct characters) * k == (length of substring). If this condition is met, increment the total count.

Walkthrough

This approach reduces the problem space by first breaking the string down. Within each valid chunk, we iterate through all possible starting points. For each starting point, we expand a window to the right, character by character, maintaining a frequency count. We can quickly discard invalid windows if any character count surpasses k. The check for a complete substring is simplified by comparing the product of distinct characters and k with the current window's length.

1class Solution {2    public int countCompleteSubstrings(String word, int k) {3        int totalCount = 0;4        int n = word.length();5        int start = 0;6        for (int i = 1; i <= n; i++) {7            if (i == n || Math.abs(word.charAt(i) - word.charAt(i - 1)) > 2) {8                // Process the chunk word.substring(start, i)9                totalCount += countInChunk(word.substring(start, i), k);10                start = i;11            }12        }13        return totalCount;14    }15 16    private int countInChunk(String s, int k) {17        int count = 0;18        int n = s.length();19        for (int i = 0; i < n; i++) {20            int[] freq = new int[26];21            int distinct = 0;22            for (int j = i; j < n; j++) {23                int charIndex = s.charAt(j) - 'a';24                if (freq[charIndex] == 0) {25                    distinct++;26                }27                freq[charIndex]++;28 29                if (freq[charIndex] > k) {30                    // This window and any larger ones starting at i are invalid31                    break;32                }33                34                if (distinct * k == (j - i + 1)) {35                    // If length is distinct * k, and no freq > k, all must be == k.36                    count++;37                }38            }39        }40        return count;41    }42}

Complexity

Time

O(N^2) - In the worst case, the entire string is one large chunk. The two nested loops over the chunk lead to a quadratic time complexity. `sum(M_i^2)` over all chunks can be `O(N^2)`.

Space

O(1) - The frequency map requires constant space.

Trade-offs

Pros

More efficient than the naive brute-force approach.
Correctly utilizes the adjacency property to partition the problem.

Cons

The O(N^2) time complexity is still too slow for the problem's constraints and will likely time out.

The most efficient solution also starts by splitting the word into valid chunks. The key improvement is how we process each chunk. Instead of checking every possible substring, we iterate through the possible number of unique characters a complete substring can have (from 1 to 26). For each number of unique characters, d, we know the exact length a complete substring must have: d * k. We can then use a fixed-size sliding window of this length to find all such substrings in linear time for that d.

Algorithm

Split into Chunks: Same as the previous approach, split word into chunks where abs(char_diff) <= 2 for all adjacent characters. This takes O(N) time.
Process Each Chunk with a Specialized Sliding Window: For each chunk s: a. Initialize a local counter for the chunk to zero. b. Iterate through the possible number of distinct characters d a complete substring can have, from d = 1 to d = 26. c. For each d, the required length of a complete substring is L = d * k. If L exceeds the chunk's length, break the loop for d. d. Use a fixed-size sliding window of length L to traverse the chunk. e. Maintain two counters for the window: distinctCount (number of unique characters) and kCount (number of characters with frequency exactly k). f. Initialize the window with the first L characters, calculating the initial distinctCount and kCount. g. Slide the window one position at a time to the right. In each step, efficiently update distinctCount and kCount in O(1) time by accounting for the character leaving and the character entering the window. h. After each slide, if distinctCount == d and kCount == d, it means the current window is a complete substring. Increment the chunk's counter.
Sum Results: The total count is the sum of counts from all chunks.

Walkthrough

This approach cleverly transforms the problem. By fixing the number of distinct characters d, we also fix the target substring length L = d * k. This allows us to use a very efficient fixed-size sliding window. The total work for a chunk of length M becomes 26 * O(M), which is O(M). Since the sum of all chunk lengths is N, the total time complexity is linear.

1class Solution {2    public int countCompleteSubstrings(String word, int k) {3        int totalCount = 0;4        int n = word.length();5        int start = 0;6        for (int i = 1; i <= n; i++) {7            if (i == n || Math.abs(word.charAt(i) - word.charAt(i - 1)) > 2) {8                totalCount += countInChunk(word.substring(start, i), k);9                start = i;10            }11        }12        return totalCount;13    }14 15    private int countInChunk(String s, int k) {16        int count = 0;17        int n = s.length();18        for (int d = 1; d <= 26; d++) {19            int len = d * k;20            if (len > n) {21                break;22            }23 24            int[] freq = new int[26];25            int distinctCount = 0;26            int kCount = 0; // count of chars with frequency == k27 28            // Initialize first window29            for (int i = 0; i < len; i++) {30                int cIdx = s.charAt(i) - 'a';31                if (freq[cIdx] == 0) distinctCount++;32                freq[cIdx]++;33                if (freq[cIdx] == k) kCount++;34                if (freq[cIdx] == k + 1) kCount--;35            }36 37            if (distinctCount == d && kCount == d) {38                count++;39            }40 41            // Slide window42            for (int i = len; i < n; i++) {43                // Add char at i44                int inIdx = s.charAt(i) - 'a';45                if (freq[inIdx] == 0) distinctCount++;46                freq[inIdx]++;47                if (freq[inIdx] == k) kCount++;48                if (freq[inIdx] == k + 1) kCount--;49 50                // Remove char at i - len51                int outIdx = s.charAt(i - len) - 'a';52                if (freq[outIdx] == k) kCount--;53                if (freq[outIdx] == k + 1) kCount++;54                freq[outIdx]--;55                if (freq[outIdx] == 0) distinctCount--;56                57                if (distinctCount == d && kCount == d) {58                    count++;59                }60            }61        }62        return count;63    }64}

Complexity

Time

O(N) - The initial split takes O(N). Processing each chunk of length `M` takes O(26 * M), which is O(M). Since the sum of all chunk lengths is `N`, the total time is O(N) + sum(O(M_i)) = O(N).

Space

O(1) - The space for the frequency map is constant (size 26), regardless of the input size.

Trade-offs

Pros

Optimal O(N) time complexity, making it highly efficient for large inputs.
Handles all constraints of the problem effectively.

Cons

The implementation is more complex, requiring careful management of the sliding window and its associated counters.

Solutions

Solution

1class Solution {2public3  int countCompleteSubstrings(String word, int k) {4    int n = word.length();5    int ans = 0;6    for (int i = 0; i < n;) {7      int j = i + 1;8      while (j < n && Math.abs(word.charAt(j) - word.charAt(j - 1)) <= 2) {9        ++j;10      }11      ans += f(word.substring(i, j), k);12      i = j;13    }14    return ans;15  }16private17  int f(String s, int k) {18    int m = s.length();19    int ans = 0;20    for (int i = 1; i <= 26 && i * k <= m; ++i) {21      int l = i * k;22      int[] cnt = new int[26];23      for (int j = 0; j < l; ++j) {24        ++cnt[s.charAt(j) - 'a'];25      }26      Map<Integer, Integer> freq = new HashMap<>();27      for (int x : cnt) {28        if (x > 0) {29          freq.merge(x, 1, Integer : : sum);30        }31      }32      if (freq.getOrDefault(k, 0) == i) {33        ++ans;34      }35      for (int j = l; j < m; ++j) {36        int a = s.charAt(j) - 'a';37        int b = s.charAt(j - l) - 'a';38        freq.merge(cnt[a], -1, Integer : : sum);39        ++cnt[a];40        freq.merge(cnt[a], 1, Integer : : sum);41        freq.merge(cnt[b], -1, Integer : : sum);42        --cnt[b];43        freq.merge(cnt[b], 1, Integer : : sum);44        if (freq.getOrDefault(k, 0) == i) {45          ++ans;46        }47      }48    }49    return ans;50  }51}

1class Solution {2public:3  int countCompleteSubstrings(string word, int k) {4    int n = word.length();5    int ans = 0;6    auto f = [&](string s) {7      int m = s.length();8      int ans = 0;9      for (int i = 1; i <= 26 && i * k <= m; ++i) {10        int l = i * k;11        int cnt[26]{};12        for (int j = 0; j < l; ++j) {13          ++cnt[s[j] - 'a'];14        }15        unordered_map<int, int> freq;16        for (int x : cnt) {17          if (x > 0) {18            freq[x]++;19          }20        }21        if (freq[k] == i) {22          ++ans;23        }24        for (int j = l; j < m; ++j) {25          int a = s[j] - 'a';26          int b = s[j - l] - 'a';27          freq[cnt[a]]--;28          cnt[a]++;29          freq[cnt[a]]++;30          freq[cnt[b]]--;31          cnt[b]--;32          freq[cnt[b]]++;33          if (freq[k] == i) {34            ++ans;35          }36        }37      }38      return ans;39    };40    for (int i = 0; i < n;) {41      int j = i + 1;42      while (j < n && abs(word[j] - word[j - 1]) <= 2) {43        ++j;44      }45      ans += f(word.substr(i, j - i));46      i = j;47    }48    return ans;49  }50};

1class Solution:2    def countCompleteSubstrings(self, word: str, k: int) -> int: def f(s: str) -> int: m = len(s) ans = 0 for i in range(1, 27): l = i * k if l > m: break cnt = Counter(s[: l]) freq = Counter(cnt . values()) ans += freq[k] == i for j in range(l, m): freq[cnt[s[j]]] -= 1 cnt[s[j]] += 1 freq[cnt[s[j]]] += 1 freq[cnt[s[j - l]]] -= 1 cnt[s[j - l]] -= 1 freq[cnt[s[j - l]]] += 1 ans += freq[k] == i return ans n = len(word) ans = i = 0 while i < n: j = i + 1 while j < n and abs(ord(word[j]) - ord(word[j - 1])) <= 2: j += 1 ans += f(word[i: j]) i = j return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int countCompleteSubstrings(String word, int k) {4    int n = word.length();5    int ans = 0;6    for (int i = 0; i < n;) {7      int j = i + 1;8      while (j < n && Math.abs(word.charAt(j) - word.charAt(j - 1)) <= 2) {9        ++j;10      }11      ans += f(word.substring(i, j), k);12      i = j;13    }14    return ans;15  }16private17  int f(String s, int k) {18    int m = s.length();19    int ans = 0;20    for (int i = 1; i <= 26 && i * k <= m; ++i) {21      int l = i * k;22      int[] cnt = new int[26];23      for (int j = 0; j < l; ++j) {24        ++cnt[s.charAt(j) - 'a'];25      }26      Map<Integer, Integer> freq = new HashMap<>();27      for (int x : cnt) {28        if (x > 0) {29          freq.merge(x, 1, Integer : : sum);30        }31      }32      if (freq.getOrDefault(k, 0) == i) {33        ++ans;34      }35      for (int j = l; j < m; ++j) {36        int a = s.charAt(j) - 'a';37        int b = s.charAt(j - l) - 'a';38        freq.merge(cnt[a], -1, Integer : : sum);39        ++cnt[a];40        freq.merge(cnt[a], 1, Integer : : sum);41        freq.merge(cnt[b], -1, Integer : : sum);42        --cnt[b];43        freq.merge(cnt[b], 1, Integer : : sum);44        if (freq.getOrDefault(k, 0) == i) {45          ++ans;46        }47      }48    }49    return ans;50  }51}

1class Solution {2public:3  int countCompleteSubstrings(string word, int k) {4    int n = word.length();5    int ans = 0;6    auto f = [&](string s) {7      int m = s.length();8      int ans = 0;9      for (int i = 1; i <= 26 && i * k <= m; ++i) {10        int l = i * k;11        int cnt[26]{};12        for (int j = 0; j < l; ++j) {13          ++cnt[s[j] - 'a'];14        }15        unordered_map<int, int> freq;16        for (int x : cnt) {17          if (x > 0) {18            freq[x]++;19          }20        }21        if (freq[k] == i) {22          ++ans;23        }24        for (int j = l; j < m; ++j) {25          int a = s[j] - 'a';26          int b = s[j - l] - 'a';27          freq[cnt[a]]--;28          cnt[a]++;29          freq[cnt[a]]++;30          freq[cnt[b]]--;31          cnt[b]--;32          freq[cnt[b]]++;33          if (freq[k] == i) {34            ++ans;35          }36        }37      }38      return ans;39    };40    for (int i = 0; i < n;) {41      int j = i + 1;42      while (j < n && abs(word[j] - word[j - 1]) <= 2) {43        ++j;44      }45      ans += f(word.substr(i, j - i));46      i = j;47    }48    return ans;49  }50};

1class Solution:2    def countCompleteSubstrings(self, word: str, k: int) -> int: def f(s: str) -> int: m = len(s) ans = 0 for i in range(1, 27): l = i * k if l > m: break cnt = Counter(s[: l]) freq = Counter(cnt . values()) ans += freq[k] == i for j in range(l, m): freq[cnt[s[j]]] -= 1 cnt[s[j]] += 1 freq[cnt[s[j]]] += 1 freq[cnt[s[j - l]]] -= 1 cnt[s[j - l]] -= 1 freq[cnt[s[j - l]]] += 1 ans += freq[k] == i return ans n = len(word) ans = i = 0 while i < n: j = i + 1 while j < n and abs(ord(word[j]) - ord(word[j - 1])) <= 2: j += 1 ans += f(word[i: j]) i = j return ans

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.