Problem

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 ofcomplete substrings of word.

A substring is a non-empty contiguous sequence of characters in a string.

Examples

Example 1

1
2
3

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

1
2
3

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^5
  • word consists 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

  1. For each possible unique character count u from 1 to 26:
    • The window size is u * k.
  2. Slide a window of size u * k over 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.
  3. If both conditions are satisfied, increment the answer.
  4. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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 }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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.