Count Substrings With K-Frequency Characters I

Medium
1369.

Count Substrings With K-Frequency Characters I

Count Substrings With K-Frequency Characters I is a medium coding problem on strings, hash table and sliding window, asked in Amazon and Google interviews.

Given a string s of lowercase English letters and an integer k, return the number of substrings of s in which at least one character appears at least k times.

Substrings at different positions count separately even when their text is equal.

Example 1

Input
s = "aabab", k = 2
Output
7
Explanation
`"aa"`, `"aab"`, `"aaba"`, `"aabab"`, `"aba"`, `"abab"` and `"bab"`.

Example 2

Input
s = "codekairo", k = 1
Output
45
Explanation
With `k = 1` every one of the 45 substrings qualifies.

Example 3

Input
s = "abcabc", k = 3
Output
0
Explanation
No letter occurs three times.

Constraints

  • 1 <= s.length <= 3000
  • 1 <= k <= s.length
  • s consists only of lowercase English letters.
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} s
 * @param {number} k
 * @return {number}
 */
var numberOfSubstrings = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Substrings With K-Frequency Characters I — Solution

Count Substrings With K-Frequency Characters I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count Substrings With K-Frequency Characters I is a medium coding problem on strings, hash table and sliding window, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • 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

Given a string s of lowercase English letters and an integer k, return the number of substrings of s in which at least one character appears at least k times.

Substrings at different positions count separately even when their text is equal.

Example 1

Input: s = "aabab", k = 2
Output: 7
Explanation: `"aa"`, `"aab"`, `"aaba"`, `"aabab"`, `"aba"`, `"abab"` and `"bab"`.

Example 2

Input: s = "codekairo", k = 1
Output: 45
Explanation: With `k = 1` every one of the 45 substrings qualifies.

Example 3

Input: s = "abcabc", k = 3
Output: 0
Explanation: No letter occurs three times.

Constraints

  • 1 <= s.length <= 3000
  • 1 <= k <= s.length
  • s consists only of lowercase English letters.

Hints for Count Substrings With K-Frequency Characters I

  1. Hint 1

    If a substring qualifies, extending it on either side keeps it qualifying.

  2. Hint 2

    For each end right, the qualifying substrings ending there are exactly those starting before some position left — find that boundary.

  3. Hint 3

    Slide a window that never qualifies: after adding s[right], only that letter can have reached k, so remove letters from the left while its count is at least k. Then the starts 0 .. left-1 all qualify; add left.

How to solve Count Substrings With K-Frequency Characters I

Keep the window [left, right] as the longest window ending at right in which every letter appears fewer than k times. Every start to the left of it gives a qualifying substring.

Approach

  1. Keep letter counts for the window, left = 0 and ans = 0.
  2. For each right, increment the count of c = s[right].
  3. While count[c] >= k, decrement the count of s[left] and advance left.
  4. Add left to ans: the substrings s[0..right], …, s[left-1..right] all contain some letter k times.

Why it works

Before s[right] is added the window has all counts below k, so after adding it only c can reach k; shrinking until c drops below k restores the invariant with the smallest possible movement. At that moment s[left-1..right] had c exactly k times, so it — and every substring starting further left — qualifies, while s[left..right] does not. Since qualifying is preserved by extension, left never moves back, giving O(n) total.

Complexity

  • Time — O(n)
  • Space — O(26)

Pitfalls

  • Add left, not right - left + 1: the window itself is the non-qualifying part.
  • Only the newly added letter can cross the threshold, so the shrink loop checks that one letter, not all 26.
  • With k = 1 every substring qualifies — the answer is n(n+1)/2.

Reference solution

Python

def numberOfSubstrings(s: str, k: int) -> int:
    cnt = [0] * 26
    left = 0
    ans = 0
    for ch in s:
        c = ord(ch) - 97
        cnt[c] += 1
        while cnt[c] >= k:
            cnt[ord(s[left]) - 97] -= 1
            left += 1
        ans += left
    return ans

Java

public static int numberOfSubstrings(String s, int k) {
    int[] cnt = new int[26];
    int left = 0, ans = 0;
    for (int right = 0; right < s.length(); right++) {
        int c = s.charAt(right) - 'a';
        cnt[c]++;
        while (cnt[c] >= k) {
            cnt[s.charAt(left) - 'a']--;
            left++;
        }
        ans += left;
    }
    return ans;
}

C++

int numberOfSubstrings(string s, int k) {
    int cnt[26] = {0};
    int left = 0, ans = 0;
    for (int right = 0; right < (int) s.size(); right++) {
        int c = s[right] - 'a';
        cnt[c]++;
        while (cnt[c] >= k) {
            cnt[s[left] - 'a']--;
            left++;
        }
        ans += left;
    }
    return ans;
}

JavaScript

var numberOfSubstrings = function(s, k) {
    var cnt = new Array(26).fill(0);
    var left = 0, ans = 0;
    for (var right = 0; right < s.length; right++) {
        var c = s.charCodeAt(right) - 97;
        cnt[c]++;
        while (cnt[c] >= k) {
            cnt[s.charCodeAt(left) - 97]--;
            left++;
        }
        ans += left;
    }
    return ans;
};

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