Scale Engineer

Count Substrings With K-Frequency Characters I

Med
#2953Time: O(n^3), where `n` is the length of the string. Generating all O(n^2) substrings and then iterating through each one (which can be up to length `n`) to count frequencies leads to a cubic time complexity.Space: O(1), as the frequency map uses a constant amount of space (size 26).
Patterns
Sliding Window
Data structures
Hash TableString

Prompt

Given a string s and an integer k, return the total number of substrings of s where at least one character appears at least k times.

 

Example 1:

Input: s = "abacb", k = 2

Output: 4

Explanation:

The valid substrings are:

  • "aba" (character 'a' appears 2 times).
  • "abac" (character 'a' appears 2 times).
  • "abacb" (character 'a' appears 2 times).
  • "bacb" (character 'b' appears 2 times).

Example 2:

Input: s = "abcde", k = 1

Output: 15

Explanation:

All substrings are valid because every character appears at least once.

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward method is to generate all possible substrings of the input string s. For each substring, we then count the frequency of its characters to determine if it satisfies the condition of having at least one character appear k or more times.

Algorithm

  • Initialize a counter ans to 0.
  • Use two nested loops with indices i and j to generate all substrings s[i..j].
  • For each substring, create a frequency map (an array of size 26).
  • Iterate through the characters of the substring to populate the frequency map.
  • Check the frequency map. If any character has a frequency of k or more, increment ans and break the check for the current substring.
  • After checking all substrings, return ans.

Walkthrough

This approach uses three nested loops. The first two loops define the start and end indices of a substring. The third loop iterates through the characters of this substring to build a frequency map. After building the map, we check if any character's frequency is at least k. If the condition is met, we increment a counter.

class Solution {    public int countSubstrings(String s, int k) {        int n = s.length();        int count = 0;        for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                // Substring is s.substring(i, j + 1)                int[] freq = new int[26];                for (int l = i; l <= j; l++) {                    freq[s.charAt(l) - 'a']++;                }                                boolean found = false;                for (int f : freq) {                    if (f >= k) {                        found = true;                        break;                    }                }                if (found) {                    count++;                }            }        }        return count;    }}

Complexity

Time

O(n^3), where `n` is the length of the string. Generating all O(n^2) substrings and then iterating through each one (which can be up to length `n`) to count frequencies leads to a cubic time complexity.

Space

O(1), as the frequency map uses a constant amount of space (size 26).

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Highly inefficient due to redundant calculations.

  • Will likely result in a 'Time Limit Exceeded' error for the given constraints.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem