Count Complete Substrings

Hard
1265.

Count Complete Substrings

Count Complete Substrings is a hard coding problem on strings, hash table and sliding window, asked in Amazon and Google interviews.

A substring of word is complete when:

  • every character that appears in it appears exactly k times, and
  • any two adjacent characters in it are at most 2 apart in the alphabet (|c1 - c2| <= 2, so a may sit next to a, b or c, but not d).

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^5
  • word consists only of lowercase English letters
  • 1 <= k <= word.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
var countCompleteSubstrings = function(word, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 k times, and
  • any two adjacent characters in it are at most 2 apart in the alphabet (|c1 - c2| <= 2, so a may sit next to a, b or c, but not d).

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

Hints for Count Complete Substrings

  1. Hint 1

    A pair of neighbours more than 2 apart can never be inside a complete substring — cut word into maximal segments at those places and solve each segment alone.

  2. Hint 2

    A complete substring with u distinct letters has length exactly u · k, and u is at most 26.

  3. Hint 3

    For each u from 1 to 26, slide a window of length u · k over the segment and keep the number of letters whose count in the window is exactly k; the window is complete when that number equals u.

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

  1. Walk word and cut it wherever |word[i] - word[i-1]| > 2; every complete substring lies inside one segment.
  2. For a segment and each u = 1..26 with u · k <= segment length: slide a window of size w = u · k.
  3. Maintain cnt[c] and exact, the number of letters with cnt[c] == k. When a letter's count moves to k, increment exact; when it moves away from k, decrement it.
  4. Whenever the window is full and exact == u, count it.
  5. 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 of k can work.
  • When a count rises from k to k + 1, the letter stops being exact — decrement exact, 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 res

Java

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