Count Complete Substrings
HardUpdated: Aug 2, 2025
Practice on:
Problem
You are given a string word and an integer k.
A substring s of word is complete if:
- Each character in
soccurs exactlyktimes. - The difference between two adjacent characters is at most
2. That is, for any two adjacent charactersc1andc2ins, the absolute difference in their positions in the alphabet is at most2.
Return the number ofcomplete substrings of word.
A substring is a non-empty contiguous sequence of characters in a string.
Examples
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: _**igig**_ ee, igig _**ee**_ , _**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: **_aaa_** bbbccc, aaa _**bbb**_ ccc, aaabbb _**ccc**_ , **_aaabbb_** ccc, aaa _**bbbccc**_ , _**aaabbbccc**_.
Constraints
1 <= word.length <= 10^5wordconsists only of lowercase English letters.1 <= k <= word.length
Solution
Method 1 – Sliding Window with Frequency Map
Intuition
We need to find all substrings where each character appears exactly k times and the difference between adjacent characters is at most 2. Since the substring can have at most 26 unique characters, we can try all possible unique character counts and use a sliding window to check for valid substrings.
Approach
- For each possible unique character count
ufrom 1 to 26:- The window size is
u * k.
- The window size is
- Slide a window of size
u * kover the string:- Use a frequency map to count occurrences of each character in the window.
- Check if all characters in the window appear exactly k times.
- Check if the difference between adjacent characters is at most 2.
- If both conditions are satisfied, increment the answer.
- Return the total count.
Code
C++
class Solution {
public:
int countCompleteSubstrings(string word, int k) {
int n = word.size(), ans = 0;
for (int u = 1; u <= 26; ++u) {
int len = u * k;
if (len > n) break;
vector<int> cnt(26, 0);
int uniq = 0, over = 0;
for (int i = 0; i < n; ++i) {
if (i >= len) {
int idx = word[i - len] - 'a';
if (--cnt[idx] == 0) uniq--;
if (cnt[idx] == k - 1) over--;
}
int idx = word[i] - 'a';
if (cnt[idx] == 0) uniq++;
if (cnt[idx] == k - 1) over++;
cnt[idx]++;
if (i >= len - 1 && uniq == u && over == u) {
bool ok = true;
for (int j = i - len + 1; j < i; ++j) {
if (abs(word[j] - word[j + 1]) > 2) {
ok = false;
break;
}
}
if (ok) ans++;
}
}
}
return ans;
}
};
Go
func countCompleteSubstrings(word string, k int) int {
n, ans := len(word), 0
for u := 1; u <= 26; u++ {
l := u * k
if l > n { break }
cnt := make([]int, 26)
uniq, over := 0, 0
for i := 0; i < n; i++ {
if i >= l {
idx := int(word[i-l] - 'a')
cnt[idx]--
if cnt[idx] == 0 { uniq-- }
if cnt[idx] == k-1 { over-- }
}
idx := int(word[i] - 'a')
if cnt[idx] == 0 { uniq++ }
if cnt[idx] == k-1 { over++ }
cnt[idx]++
if i >= l-1 && uniq == u && over == u {
ok := true
for j := i-l+1; j < i; j++ {
if abs(int(word[j])-int(word[j+1])) > 2 {
ok = false
break
}
}
if ok { ans++ }
}
}
}
return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
Java
class Solution {
public int countCompleteSubstrings(String word, int k) {
int n = word.length(), ans = 0;
for (int u = 1; u <= 26; ++u) {
int len = u * k;
if (len > n) break;
int[] cnt = new int[26];
int uniq = 0, over = 0;
for (int i = 0; i < n; ++i) {
if (i >= len) {
int idx = word.charAt(i - len) - 'a';
if (--cnt[idx] == 0) uniq--;
if (cnt[idx] == k - 1) over--;
}
int idx = word.charAt(i) - 'a';
if (cnt[idx] == 0) uniq++;
if (cnt[idx] == k - 1) over++;
cnt[idx]++;
if (i >= len - 1 && uniq == u && over == u) {
boolean ok = true;
for (int j = i - len + 1; j < i; ++j) {
if (Math.abs(word.charAt(j) - word.charAt(j + 1)) > 2) {
ok = false;
break;
}
}
if (ok) ans++;
}
}
}
return ans;
}
}
Kotlin
class Solution {
fun countCompleteSubstrings(word: String, k: Int): Int {
val n = word.length
var ans = 0
for (u in 1..26) {
val len = u * k
if (len > n) break
val cnt = IntArray(26)
var uniq = 0
var over = 0
for (i in 0 until n) {
if (i >= len) {
val idx = word[i - len] - 'a'
cnt[idx]--
if (cnt[idx] == 0) uniq--
if (cnt[idx] == k - 1) over--
}
val idx = word[i] - 'a'
if (cnt[idx] == 0) uniq++
if (cnt[idx] == k - 1) over++
cnt[idx]++
if (i >= len - 1 && uniq == u && over == u) {
var ok = true
for (j in i - len + 1 until i) {
if (kotlin.math.abs(word[j] - word[j + 1]) > 2) {
ok = false
break
}
}
if (ok) ans++
}
}
}
return ans
}
}
Python
class Solution:
def countCompleteSubstrings(self, word: str, k: int) -> int:
n, ans = len(word), 0
for u in range(1, 27):
l = u * k
if l > n: break
cnt = [0] * 26
uniq = over = 0
for i in range(n):
if i >= l:
idx = ord(word[i - l]) - ord('a')
cnt[idx] -= 1
if cnt[idx] == 0: uniq -= 1
if cnt[idx] == k - 1: over -= 1
idx = ord(word[i]) - ord('a')
if cnt[idx] == 0: uniq += 1
if cnt[idx] == k - 1: over += 1
cnt[idx] += 1
if i >= l - 1 and uniq == u and over == u:
ok = True
for j in range(i - l + 1, i):
if abs(ord(word[j]) - ord(word[j + 1])) > 2:
ok = False
break
if ok: ans += 1
return ans
Rust
impl Solution {
pub fn count_complete_substrings(word: String, k: i32) -> i32 {
let n = word.len();
let w = word.as_bytes();
let mut ans = 0;
for u in 1..=26 {
let l = u * k as usize;
if l > n { break; }
let mut cnt = [0; 26];
let (mut uniq, mut over) = (0, 0);
for i in 0..n {
if i >= l {
let idx = (w[i - l] - b'a') as usize;
cnt[idx] -= 1;
if cnt[idx] == 0 { uniq -= 1; }
if cnt[idx] == k - 1 { over -= 1; }
}
let idx = (w[i] - b'a') as usize;
if cnt[idx] == 0 { uniq += 1; }
if cnt[idx] == k - 1 { over += 1; }
cnt[idx] += 1;
if i + 1 >= l && uniq == u && over == u {
let mut ok = true;
for j in (i + 1 - l)..i {
if (w[j] as i32 - w[j + 1] as i32).abs() > 2 {
ok = false;
break;
}
}
if ok { ans += 1; }
}
}
}
ans
}
}
TypeScript
class Solution {
countCompleteSubstrings(word: string, k: number): number {
const n = word.length;
let ans = 0;
for (let u = 1; u <= 26; u++) {
const l = u * k;
if (l > n) break;
const cnt = Array(26).fill(0);
let uniq = 0, over = 0;
for (let i = 0; i < n; i++) {
if (i >= l) {
const idx = word.charCodeAt(i - l) - 97;
cnt[idx]--;
if (cnt[idx] === 0) uniq--;
if (cnt[idx] === k - 1) over--;
}
const idx = word.charCodeAt(i) - 97;
if (cnt[idx] === 0) uniq++;
if (cnt[idx] === k - 1) over++;
cnt[idx]++;
if (i >= l - 1 && uniq === u && over === u) {
let ok = true;
for (let j = i - l + 1; j < i; j++) {
if (Math.abs(word.charCodeAt(j) - word.charCodeAt(j + 1)) > 2) {
ok = false;
break;
}
}
if (ok) ans++;
}
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(26 * n), as we try all unique character counts and slide a window over the string. - 🧺 Space complexity:
O(26), for the frequency map.