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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Substrings With K-Frequency Characters I

Difficulty: Medium

Problem 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.

Key Insights

  • Substrings are defined as continuous sequences of characters within the string.
  • A character's frequency in a substring needs to be tracked to determine if it meets the k-frequency requirement.
  • The solution can leverage a sliding window approach to efficiently count substrings while maintaining a frequency count of characters.
  • Edge cases include scenarios where k is 1, which makes all substrings valid.

Space and Time Complexity

Time Complexity: O(n^2) - We need to evaluate all possible substrings in the worst case. Space Complexity: O(1) - The frequency count only needs to store counts for 26 lowercase English letters.

Solution

The algorithm employs a sliding window technique combined with a frequency count of characters. It iterates through all possible starting points for substrings and expands the end of the window while updating the character frequency. For each valid window where at least one character meets the k-frequency condition, the number of valid substrings is counted by considering all possible end positions from the current start.

Code Solutions

def countSubstrings(s: str, k: int) -> int:
    n = len(s)
    result = 0
    
    for start in range(n):
        freq = {}
        for end in range(start, n):
            char = s[end]
            if char in freq:
                freq[char] += 1
            else:
                freq[char] = 1
            
            # Check if any character's frequency is at least k
            if any(count >= k for count in freq.values()):
                result += 1
    
    return result
← Back to All Questions