Count Substrings With K-Frequency Characters I

MEDIUM

Description

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

Checkout 3 different approaches to solve Count Substrings With K-Frequency Characters I. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Enumeration

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as the frequency map uses a constant amount of space (size 26).

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count Substrings With K-Frequency Characters I. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Count Substrings With K-Frequency Characters I

Patterns:

Sliding Window

Data Structures:

Hash TableString