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 II

Number: 3499

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

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

Key Insights

  • Instead of directly counting the valid substrings, count the substrings that are invalid (i.e. in which no character appears k or more times) and subtract from the total number of substrings.
  • A two-pointer (sliding window) technique can efficiently determine, for every start index, the longest valid window (for the invalid condition) where every character’s frequency is less than k.
  • Maintain a frequency counter for the current window and a counter (countAtK) that tracks how many characters have reached frequency k.
  • When adding a new character makes one of the counts reach k (thus violating the “invalid” condition), slide the window’s left index until the condition is restored.
  • Total valid substrings = Total substrings – Count of substrings where no character appears at least k times.

Space and Time Complexity

Time Complexity: O(n) – the two-pointer approach processes each character at most twice. Space Complexity: O(1) – only a fixed frequency array (size 26) is used.

Solution

The solution first calculates the total number of substrings in s, which is n*(n+1)/2. It then uses a sliding window to count the number of substrings that do not have any character appearing k or more times (“invalid substrings”). As soon as a character’s frequency in the window reaches k, the window is contracted from the left until the frequency falls below k. The count of substrings ending at the current index (which remain “invalid”) is added based on the current window size. Finally, subtracting the count of invalid substrings from the total number yields the number of valid substrings.

Data Structures Used:

  • Frequency array of fixed size (26) to track counts of each character.
  • Two pointers (left and right) for sliding window management.

Algorithmic Approach:

  • Sliding window (two-pointer) to expand/contract the current substring window based on the frequency condition.
  • Complementary counting by subtracting invalid substrings from the total number.

Key Trick:

  • Instead of counting valid substrings directly, count the ones that do not satisfy the condition in a single pass and subtract from the total, converting a complex validity condition into a manageable invariant.

Code Solutions

# Python solution using sliding window and complementary counting
class Solution:
    def countSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        # Total number of substrings in s
        total_substrings = n * (n + 1) // 2
        
        # Count of substrings where no character appears k or more times
        invalid_substrings = 0
        
        left = 0
        countAtK = 0  # Number of characters that have reached frequency k in the current window
        freq = [0] * 26  # Frequency array for lowercase letters
        
        for right in range(n):
            index = ord(s[right]) - ord('a')
            freq[index] += 1
            # If the frequency reaches exactly k, update countAtK
            if freq[index] == k:
                countAtK += 1
                
            # If any character in the window has frequency k, shrink the window from the left
            while countAtK > 0 and left <= right:
                left_index = ord(s[left]) - ord('a')
                # If before removing s[left], its frequency is exactly k then decrease countAtK
                if freq[left_index] == k:
                    countAtK -= 1
                freq[left_index] -= 1
                left += 1
            # Now the window [left, right] is valid under the invalid condition (no char frequency >= k)
            invalid_substrings += (right - left + 1)
        
        # The valid substrings are total substrings minus invalid substrings
        return total_substrings - invalid_substrings

# Example usage:
# sol = Solution()
# print(sol.countSubstrings("abacb", 2))  # Expected output: 4
← Back to All Questions