Count Complete Substrings — Solution in Python, Java & C++
Count Complete Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count Complete Substrings is a hard coding problem on strings, hash table and sliding window, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Hash Table, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A substring of word is complete when:
- every character that appears in it appears exactly
ktimes, and - any two adjacent characters in it are at most 2 apart in the alphabet (
|c1 - c2| <= 2, soamay sit next toa,borc, but notd).
Return the number of complete substrings of word. Substrings at different positions are counted separately.
Example 1
Input: word = "aabbcc", k = 2
Output: 6
Explanation: `aa`, `bb`, `cc`, `aabb`, `bbcc` and `aabbcc`.
Example 2
Input: word = "abcabc", k = 1
Output: 15
Explanation: Every substring of length 1, 2 or 3 has distinct letters with neighbours at most 2 apart.
Example 3
Input: word = "zza", k = 2
Output: 1
Explanation: `z` and `a` are too far apart to be neighbours, so only `zz` counts.
Constraints
1 <= word.length <= 10^5word consists only of lowercase English letters1 <= k <= word.length
Hints for Count Complete Substrings
Hint 1
A pair of neighbours more than 2 apart can never be inside a complete substring — cut
wordinto maximal segments at those places and solve each segment alone.Hint 2
A complete substring with
udistinct letters has length exactlyu · k, anduis at most 26.Hint 3
For each
ufrom 1 to 26, slide a window of lengthu · kover the segment and keep the number of letters whose count in the window is exactlyk; the window is complete when that number equalsu.
How to solve Count Complete Substrings
Split at the illegal neighbour pairs, then fix the number of distinct letters u: the window length is forced to u · k, so a fixed-size sliding window with letter counts checks every candidate in O(1) amortised time.
Approach
- Walk
wordand cut it wherever|word[i] - word[i-1]| > 2; every complete substring lies inside one segment. - For a segment and each
u = 1..26withu · k <=segment length: slide a window of sizew = u · k. - Maintain
cnt[c]andexact, the number of letters withcnt[c] == k. When a letter's count moves tok, incrementexact; when it moves away fromk, decrement it. - Whenever the window is full and
exact == u, count it. - Sum over all segments and all
u.
Why it works
If u letters each occur exactly k times in a window of length u · k, they fill the whole window, so no other letter is present and the window is complete; conversely a complete window with u distinct letters has exactly this shape. Each complete substring has exactly one u, so it is counted once, and the neighbour condition holds because it lies inside a segment.
Complexity
- Time —
O(26 · n) - Space —
O(26)
Pitfalls
- Forgetting the neighbour rule, or applying it only at window boundaries instead of splitting the string.
- Testing every window length is
O(n^2); only the 26 multiples ofkcan work. - When a count rises from
ktok + 1, the letter stops being exact — decrementexact, do not leave it.
Reference solution
Python
def countCompleteSubstrings(word: str, k: int) -> int:
n = len(word)
total = 0
start = 0
for end in range(1, n + 1):
if end == n or abs(ord(word[end]) - ord(word[end - 1])) > 2:
total += _complete_in_segment(word, start, end, k)
start = end
return total
def _complete_in_segment(word, lo, hi, k):
res = 0
for u in range(1, 27):
w = u * k
if w > hi - lo:
break
cnt = [0] * 26
exact = 0
for i in range(lo, hi):
c = ord(word[i]) - 97
cnt[c] += 1
if cnt[c] == k:
exact += 1
elif cnt[c] == k + 1:
exact -= 1
if i - lo >= w:
d = ord(word[i - w]) - 97
if cnt[d] == k:
exact -= 1
cnt[d] -= 1
if cnt[d] == k:
exact += 1
if i - lo >= w - 1 and exact == u:
res += 1
return resJava
static int ccsSegment(String word, int lo, int hi, int k) {
int res = 0;
for (int u = 1; u <= 26 && (long) u * k <= hi - lo; u++) {
int w = u * k;
int[] cnt = new int[26];
int exact = 0;
for (int i = lo; i < hi; i++) {
int c = word.charAt(i) - 'a';
cnt[c]++;
if (cnt[c] == k) exact++;
else if (cnt[c] == k + 1) exact--;
if (i - lo >= w) {
int d = word.charAt(i - w) - 'a';
if (cnt[d] == k) exact--;
cnt[d]--;
if (cnt[d] == k) exact++;
}
if (i - lo >= w - 1 && exact == u) res++;
}
}
return res;
}
public static int countCompleteSubstrings(String word, int k) {
int n = word.length(), total = 0, start = 0;
for (int end = 1; end <= n; end++) {
if (end == n || Math.abs(word.charAt(end) - word.charAt(end - 1)) > 2) {
total += ccsSegment(word, start, end, k);
start = end;
}
}
return total;
}C++
static int ccsSegment(const string& word, int lo, int hi, int k) {
int res = 0;
for (int u = 1; u <= 26 && (long long)u * k <= hi - lo; u++) {
int w = u * k;
int cnt[26] = {0};
int exact = 0;
for (int i = lo; i < hi; i++) {
int c = word[i] - 'a';
cnt[c]++;
if (cnt[c] == k) exact++;
else if (cnt[c] == k + 1) exact--;
if (i - lo >= w) {
int d = word[i - w] - 'a';
if (cnt[d] == k) exact--;
cnt[d]--;
if (cnt[d] == k) exact++;
}
if (i - lo >= w - 1 && exact == u) res++;
}
}
return res;
}
int countCompleteSubstrings(string word, int k) {
int n = word.size(), total = 0, start = 0;
for (int end = 1; end <= n; end++) {
if (end == n || abs(word[end] - word[end - 1]) > 2) {
total += ccsSegment(word, start, end, k);
start = end;
}
}
return total;
}JavaScript
function ccsSegment(word, lo, hi, k) {
var res = 0;
for (var u = 1; u <= 26 && u * k <= hi - lo; u++) {
var w = u * k;
var cnt = new Array(26).fill(0);
var exact = 0;
for (var i = lo; i < hi; i++) {
var c = word.charCodeAt(i) - 97;
cnt[c]++;
if (cnt[c] === k) exact++;
else if (cnt[c] === k + 1) exact--;
if (i - lo >= w) {
var d = word.charCodeAt(i - w) - 97;
if (cnt[d] === k) exact--;
cnt[d]--;
if (cnt[d] === k) exact++;
}
if (i - lo >= w - 1 && exact === u) res++;
}
}
return res;
}
var countCompleteSubstrings = function(word, k) {
var n = word.length, total = 0, start = 0;
for (var end = 1; end <= n; end++) {
if (end === n || Math.abs(word.charCodeAt(end) - word.charCodeAt(end - 1)) > 2) {
total += ccsSegment(word, start, end, k);
start = end;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets