3329. Count Substrings With K-Frequency Characters II 🔒

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.

Intuition

To solve this problem efficiently, we can use a sliding window technique. The idea is to dynamically adjust a window of characters within the string s while keeping track of character frequencies.

Sliding Window Setup: We maintain two pointers, l and r, where l is the left boundary and r is the right boundary of our sliding window. We traverse the string with r moving forward, adding the character at position r to the current window.
Character Frequency Count: For each character added to the window at r, we update its frequency in a Counter.
Adjust Left Boundary: When a character's count within the window becomes k or more, it means any substring starting before l with current r satisfies the condition that at least one character appears at least k times. Thus, we need to adjust the left boundary l to remove characters from the window until the character count falls below k.
Count Substrings: For every valid window configuration where the right boundary ends at r, all possible starting points [0..l-1] generate valid substrings. Therefore, we add l to our answer, as it represents the number of valid starting points.

This approach efficiently calculates the number of desired substrings by making optimal use of the sliding window technique and character frequency count, avoiding unnecessary recalculations.

Learn more about Sliding Window patterns.

Solution Approach

The solution utilizes the Sliding Window technique coupled with a frequency counter to efficiently find the number of valid substrings. Here's a detailed walkthrough:

Initialize Data Structures:
- A Counter is used to track the frequency of each character within the current window.
- An integer l is used to mark the start of the window.
- An integer ans is initialized to accumulate the total count of valid substrings.
Iterate Through the String:
- As we iterate over each character c in the string with the right endpoint r, increment the count of this character in the Counter.
Adjust the Left Boundary:
- If the count of the current character c in the Counter reaches k, it indicates that the substring from a previous left boundary to current r has a character appearing k or more times.
- To ensure all substrings counted are valid, increment the left boundary l until the count of c becomes less than k. This is done by decrementing the count of the character at the current left boundary and moving l one step forward.
Count Valid Substrings:
- For every position r, all substrings starting between indices [0...l-1] and ending at r are valid. Hence, add l to ans.
Return the Result:
- After processing all characters, ans will hold the total count of substrings where at least one character appears at least k times.

This approach is efficient with a time complexity of O(n) due to the linear traversal and adjustment of the window, where n is the length of the string. It ensures that each character is processed in a constant amount of work per step, leveraging the power of the sliding window pattern.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution with a small example where s = "aaabbc" and k = 2.

Initialize Data Structures:
- We start with an empty Counter to track character frequencies, a left pointer l = 0 to mark the start of the sliding window, and an ans = 0 to accumulate the count of valid substrings.
Iterate Through the String:
- Iteration 1 (r = 0, character = 'a'):
  Increase the count of 'a' in the Counter, resulting in {'a': 1}. The count is less than k, so no adjustment of l is needed.
- Iteration 2 (r = 1, character = 'a'):
  Update the Counter to {'a': 2}. Now, 'a' appears at least k times within the window [0, 1]. All substrings ending at 1 and starting from [0...0] are valid. Add l = 1 to ans. Thus, ans = 1.
- Iteration 3 (r = 2, character = 'a'):
  Now, the Counter is {'a': 3}. 'a' still appears at least k times, so include valid substrings ending at 2 and starting from [0...0]. Add l = 1 to ans, making ans = 2.
- Iteration 4 (r = 3, character = 'b'):
  Update the Counter to {'a': 3, 'b': 1}. 'b' does not meet k yet, so there's no need to adjust l. Add l = 1 to ans, resulting in ans = 3 as substrings [0...0] to 3 are valid.
- Iteration 5 (r = 4, character = 'b'):
  The Counter becomes {'a': 3, 'b': 2}. Now, 'b' appears k times. Adjust l to ensure valid substrings because a character reaches its limit. Add l = 1 to ans, making ans = 4.
- Iteration 6 (r = 5, character = 'c'):
  Update the Counter to {'a': 3, 'b': 2, 'c': 1}. Neither 'c' nor 'a' is adjusted to need l changes, so add l = 1 to the ans, resulting in ans = 5.
Return the Result:
- After iterating through the string, the total number of valid substrings is stored in ans, which is 5.

This example showcases how the sliding window and frequency counter work together to efficiently count substrings where at least one character appears at least k times.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def numberOfSubstrings(self, s: str, k: int) -> int:
5        # Initialize a Counter to keep track of character frequencies
6        character_count = Counter()
7      
8        # Initialize answer and the left pointer of the sliding window
9        answer = 0
10        left_pointer = 0
11      
12        # Iterate over each character in the string
13        for character in s:
14            # Increment the frequency count for the current character
15            character_count[character] += 1
16          
17            # If the frequency of the current character is at least k
18            while character_count[character] >= k:
19                # Decrement the frequency of the character at the left pointer
20                character_count[s[left_pointer]] -= 1
21                # Move the left pointer to the right
22                left_pointer += 1
23          
24            # Add the number of valid starting positions for substrings ending at current position
25            answer += left_pointer
26      
27        # Return the accumulated answer
28        return answer
29

1class Solution {
2    public long numberOfSubstrings(String s, int k) {
3        int[] characterCount = new int[26]; // Array to count occurrences of each character
4        long result = 0; // Variable to store the final result (number of substrings)
5      
6        // Two pointers approach: 'left' and 'right'
7        for (int left = 0, right = 0; right < s.length(); ++right) {
8            int currentCharIndex = s.charAt(right) - 'a'; // Convert character to index
9            ++characterCount[currentCharIndex]; // Increase count for the current character
10          
11            // Check if the current character count is at least 'k'
12            while (characterCount[currentCharIndex] >= k) {
13                --characterCount[s.charAt(left) - 'a']; // Decrease count for character at 'left'
14                left++; // Move the left pointer for a new potential start of the substring
15            }
16          
17            // Add 'left' to the result, this represents all valid substrings ending at 'right'
18            result += left;
19        }
20      
21        return result; // Return the total count of valid substrings
22    }
23}
24

1class Solution {
2public:
3    long long numberOfSubstrings(string s, int k) {
4        // n is the length of the input string s
5        int n = s.size();
6        // ans will store the total number of valid substrings
7        long long ans = 0;
8        // l is the left pointer of the sliding window
9        int l = 0;
10        // cnt is an array to keep track of the count of each character in the current window
11        int cnt[26]{}; // Initialize count array to 0 for each of the 26 lowercase letters
12      
13        // Iterate over each character in the string s
14        for (char& c : s) {
15            // Increment the count for the current character
16            ++cnt[c - 'a'];
17          
18            // Shift the left pointer l until the current character count is less than k
19            while (cnt[c - 'a'] >= k) {
20                // Decrement the count of the character at the current left position
21                --cnt[s[l++] - 'a'];
22            }
23          
24            // Add the number of valid substrings ending at the current position
25            ans += l;
26        }
27      
28        // Return the total number of valid substrings
29        return ans;
30    }
31};
32

1/**
2 * This function calculates the number of substrings where each character appears at least k times.
3 * @param s - The input string consisting only of lowercase English letters.
4 * @param k - The minimum number of times each character should appear in a substring.
5 * @returns The total number of valid substrings.
6 */
7function numberOfSubstrings(s: string, k: number): number {
8    let ans = 0; // Initialize result to count valid substrings.
9    let l = 0; // Left pointer for the sliding window.
10    const count: number[] = Array(26).fill(0); // Array to keep the count of each character in the window.
11
12    // Iterate over each character in the string.
13    for (const char of s) {
14        const currentIndex = char.charCodeAt(0) - 97; // Map char to 0-based index (a=0, b=1, ..., z=25).
15        count[currentIndex]++; // Increment the count for the current character.
16
17        // Check if the count of the current character meets or exceeds k.
18        while (count[currentIndex] >= k) {
19            // If so, contract the window from the left.
20            count[s[l++].charCodeAt(0) - 97]--; // Decrease count of the character at the left pointer and move left pointer.
21        }
22
23        ans += l; // Add the number of valid substrings ending at the current position.
24    }
25
26    return ans; // Return the total number of valid substrings.
27}
28

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string s. This is because each character in the string is processed at most twice. The outer loop processes each character once, and the inner while loop ensures that each character in the subarray increasing l is also processed at most once. Thus, the entire string is traversed with linear complexity.

The space complexity is O(|Σ|), where Σ is the character set, which in the given context is the set of lowercase English letters. This results in |Σ| = 26, as there are 26 possible characters at most, and the Counter object stores these counts, making the space complexity constant at O(26).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: