We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Substrings With K-Frequency Characters I

Number: 3502

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a string s and an integer k, count the total number of non-empty substrings such that in each substring at least one character appears at least k times.

Key Insights

  • The condition “at least one character appears at least k times” enables an early stopping point when examining substrings starting at a given index.
  • For each starting index, iterate through the substring until the condition is met. Once met at a particular end index, all longer substrings (with that start) will also be valid.
  • Use a frequency counter (an array or dictionary) to track character counts as the window expands.
  • This approach avoids re-checking every substring fully and reduces redundant work.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case (n is the length of s)
Space Complexity: O(1) since the frequency counter size is fixed (26 for lowercase letters)

Solution

We use a sliding window or two-pointer technique starting at every index of the string. For each starting index, maintain a frequency counter for the substring as it grows. Once any character's count in the current substring becomes k, every extension of that substring will also be valid. Thus, you can add (n - current_end_index) to your answer and break out of the inner loop to move to the next starting index. The key data structure is a fixed-size integer array (of length 26) to track character frequency.

Code Solutions

# Python solution for Count Substrings With K-Frequency Characters I

def countSubstringsWithKFrequencyChars(s, k):
    n = len(s)
    total_valid = 0
    # iterate through each possible starting index
    for start in range(n):
        freq = [0] * 26  # frequency array for lowercase letters
        # iterate from the starting index to the end of the string
        for end in range(start, n):
            idx = ord(s[end]) - ord('a')
            freq[idx] += 1  # update frequency for character at end
            # check if any character meets the k frequency condition
            if freq[idx] == k:
                # if condition met, all substrings from this start to end of string are valid
                total_valid += (n - end)
                break  # move to next starting index since no need to extend further
    return total_valid

# Example usage:
print(countSubstringsWithKFrequencyChars("abacb", 2))  # Expected output: 4
← Back to All Questions