Facebook Pixel

3261. Count Substrings That Satisfy K-Constraint II

HardArrayStringBinary SearchPrefix SumSliding Window
Leetcode Link

Problem Description

You are given a binary string s and an integer k.

Additionally, you're provided with a 2D integer array queries, where each queries[i] is defined as [l_i, r_i].

A binary string meets the k-constraint if at least one of these conditions holds true:

  • The number of 0s in the string should not exceed k.
  • The number of 1s in the string should not exceed k.

Your task is to return an integer array answer, where answer[i] represents the number of substrings in s[l_i..r_i] that satisfy the k-constraint.

Intuition

To solve the problem, we utilize a Sliding Window approach combined with a Prefix Sum to handle each query efficiently.

  1. Sliding Window Technique:

    • We maintain a window [i, j] as we iterate through the string s to efficiently count 0's and 1's.
    • As we extend the window by moving j, we keep track of the count of 0's and 1's within that window using two counters, cnt[0] and cnt[1].
    • We ensure either of these counts does not exceed k by adjusting the starting point i when necessary.

  2. Using Array d:

    • Array d records the positions where the window fails to satisfy the k-constraint.
    • d[i] stores the first index to the right of i where the k-constraint condition fails.

  3. Prefix Sum pre:

    • We use a prefix sum array pre to efficiently calculate the number of valid substrings ending at each position j.
    • pre[j + 1] records how many valid substrings can end at position j.

Whenever the window does not satisfy the condition (both cnt[0] and cnt[1] exceed k), we adjust the starting index i to maintain a valid window.

For each query [l, r], we calculate:

  • Substrings entirely within the [l, p) range by using a formula based on the sequence sum: (1 + p - l) * (p - l) / 2.
  • Substrings starting within [p, r] range using prefix sums: pre[r + 1] - pre[p].

These calculations allow us to efficiently count substrings in s[l_i..r_i] that satisfy the k-constraint for each query.

Learn more about Binary Search, Prefix Sum and Sliding Window patterns.

Solution Approach

Sliding Window + Prefix Sum Strategy

To efficiently solve the problem given the constraints, we employ a combination of the Sliding Window technique and Prefix Sum array.

  1. Initialize Data Structures:

    • cnt = [0, 0]: This keeps track of the count of 0's and 1's within our sliding window.
    • i, n = 0, len(s): i is the start index of our window, and n is the length of the string s.
    • d = [n] * n: An array to record the first position beyond which the k-constraint fails when starting from a given index i.
    • pre = [0] * (n + 1): A prefix sum array to store the count of satisfying substrings ending at each index.

  2. Slide the Window:

    • Iterate through the string using index j.
    • Increment the respective count in cnt for the character at index j.
    • If both cnt[0] > k and cnt[1] > k, it means the substring [i, j] does not satisfy the constraints. Therefore, set d[i] = j, reduce the count at i and increment i to move the starting point of the window forward.
    • Calculate the number of valid substrings ending at j, which is j - i + 1, and accumulate it in the pre array.

  3. Calculate Results for Each Query:

    • For each query [l, r], determine the end position p where validity fails, which is p = min(r + 1, d[l]).
    • Calculate all substrings satisfying the constraint from l to p - 1 using (1 + p - l) * (p - l) // 2.
    • Compute valid substrings starting from p to r using the prefix sums: pre[r + 1] - pre[p].
    • Sum these two results to get the answer for the query.

This combination of a dynamic sliding window and pre-computed prefix sums allows the computation of constraints efficiently for potentially large input sizes and numerous queries.

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 consider a small example to illustrate the solution approach:

Given:

  • Binary string s = "11010"
  • Integer k = 1
  • Queries: [[0, 2], [1, 4]]

The goal is to determine the number of substrings for each query that meet the k-constraint: either number of 0's or number of 1's does not exceed k.

Solution Approach Breakdown:

  1. Initialize Data Structures:

    • cnt = [0, 0]: Tracks counts of 0's and 1's.
    • i = 0: Starting index of the sliding window.
    • n = 5: Length of the string s.
    • d = [5, 5, 5, 5, 5]: Records first position violating the k-constraint.
    • pre = [0, 0, 0, 0, 0, 0]: Stores counts of valid substrings ending at each index.

  2. Slide the Window:

    • Iterate over s with j:

    • For j = 0: s[j] = '1'

      • cnt = [0, 1]
      • Valid as cnt[0] <= k and cnt[1] <= k. Update pre[1] = 1.

    • For j = 1: s[j] = '1'

      • cnt = [0, 2]
      • Invalid since cnt[1] > k. Set d[i] = j = 1, adjust window by incrementing i, reducing count at s[i] = '1'. i = 1, cnt = [0, 1]. Update pre[2] = 2.

    • For j = 2: s[j] = '0'

      • cnt = [1, 1]
      • Valid. Update pre[3] = 3.

    • For j = 3: s[j] = '1'

      • cnt = [1, 2]
      • Invalid. Set d[i] = j = 3, increment i, reduce count at s[i] = '1'. i = 2, cnt = [1, 1]. Update pre[4] = 4.

    • For j = 4: s[j] = '0'

      • cnt = [2, 1]
      • Invalid. Set d[i] = j = 4, increment i, reduce count at s[i] = '0'. i = 3, cnt = [1, 1]. Update pre[5] = 5.

  3. Calculate Results for Each Query:

    • Query ([0, 2]):

      • p = min(3, d[0]) = 3
      • Substrings entirely within [0, p): (1 + 3 - 0) * (3 - 0) // 2 = 6
      • Substrings starting within [3, 2]: pre[3] - pre[3] = 0
      • Total = (6 + 0 = 6)

    • Query ([1, 4]):

      • p = min(5, d[1]) = 4
      • Substrings entirely within [1, p): (1 + 4 - 1) * (4 - 1) // 2 = 6
      • Substrings starting within [4, 4]: pre[5] - pre[4] = 1
      • Total = (6 + 1 = 7)

Final Result:

  • For Query [0, 2], the number of valid substrings: 6
  • For Query [1, 4], the number of valid substrings: 7

The answer array output is [6, 7].

Solution Implementation

1from typing import List
2
3class Solution:
4    def countKConstraintSubstrings(
5        self, s: str, k: int, queries: List[List[int]]
6    ) -> List[int]:
7        # Initialize count of '0's and '1's as a list: [count_of_0, count_of_1]
8        count = [0, 0]
9        start_index, length_of_s = 0, len(s)
10      
11        # d will store the rightmost index for the current valid substring start
12        max_index_for_start = [length_of_s] * length_of_s
13      
14        # pre will hold the prefix sums of valid substrings' lengths
15        prefix_sums = [0] * (length_of_s + 1)
16      
17        # Iterate through the string, interpreting each character as an integer
18        for end_index, char_as_int in enumerate(map(int, s)):
19            # Increment the appropriate count for '0' or '1'
20            count[char_as_int] += 1
21
22            # When both '0's and '1's exceed the allowed count k
23            while count[0] > k and count[1] > k:
24                # Set the max right boundary for the current start_index
25                max_index_for_start[start_index] = end_index
26              
27                # Decrease count of the character at start_index and move the start index forward
28                count[int(s[start_index])] -= 1
29                start_index += 1
30
31            # Update the prefix sum of valid substrings up to the current end_index
32            prefix_sums[end_index + 1] = prefix_sums[end_index] + end_index - start_index + 1
33
34        results = []
35      
36        # Process each query to calculate the number of valid substrings
37        for left, right in queries:
38            # Determine the maximum valid right index for the current left query start
39            valid_right_boundary = min(right + 1, max_index_for_start[left])
40          
41            # Calculate all possible substrings within the query range
42            all_substrings_in_range = (1 + valid_right_boundary - left) * (valid_right_boundary - left) // 2
43
44            # Calculate the prefix sum difference for the excess range
45            prefix_sum_difference = prefix_sums[right + 1] - prefix_sums[valid_right_boundary]
46          
47            # Append the total number of valid substrings to the results list
48            results.append(all_substrings_in_range + prefix_sum_difference)
49      
50        return results
51
1import java.util.Arrays;
2
3class Solution {
4    public long[] countKConstraintSubstrings(String s, int k, int[][] queries) {
5        // Store count of '0's and '1's
6        int[] count = new int[2];
7        int n = s.length();
8
9        // Array to store the minimum index where the substring breaks the constraint
10        int[] d = new int[n];
11        Arrays.fill(d, n); // Initially fill with the length of the string
12
13        // Array to store prefix sums of valid substring lengths
14        long[] prefix = new long[n + 1];
15
16        // Sliding window approach to find valid substrings
17        for (int i = 0, j = 0; j < n; ++j) {
18            // Increment the count for the current character
19            count[s.charAt(j) - '0']++;
20
21            // Check if both counts exceed k, adjust the window if necessary
22            while (count[0] > k && count[1] > k) {
23                d[i] = j; // Mark the breaking index
24                count[s.charAt(i++) - '0']--; // Decrease count for character at i
25            }
26
27            // Calculate prefix sum of valid substrings ending at j
28            prefix[j + 1] = prefix[j] + j - i + 1;
29        }
30
31        int numQueries = queries.length;
32        long[] result = new long[numQueries]; // Array to store results for each query
33
34        // Process each query
35        for (int i = 0; i < numQueries; ++i) {
36            int left = queries[i][0], right = queries[i][1];
37
38            // Find the minimum breaking index within the range to respect the constraint
39            int breakingIndex = Math.min(right + 1, d[left]);
40
41            // Calculate number of valid substrings entirely within the range [left, breakingIndex)
42            long partialCount = (1L + breakingIndex - left) * (breakingIndex - left) / 2;
43
44            // Add the count of valid substrings that start after the breaking index but end before or at `right`
45            long additionalCount = prefix[right + 1] - prefix[breakingIndex];
46
47            // Total count for the current query
48            result[i] = partialCount + additionalCount;
49        }
50
51        return result;
52    }
53}
54
1class Solution {
2public:
3    vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>>& queries) {
4        // Array to keep count of '0's and '1's in the substring
5        int count[2] = {};
6        int n = s.size();
7      
8        // Array to store the end position for the sliding window
9        vector<int> endIndices(n, n);
10      
11        // Prefix sum array for pre-calculating substring sums
12        vector<long long> prefixSum(n + 1, 0);
13      
14        // Pointer to manage the start of the current valid window
15        for (int i = 0, j = 0; j < n; ++j) {
16            // Update count for the current character
17            count[s[j] - '0']++;
18          
19            // If both '0's and '1's exceed k, shrink the window from the left
20            while (count[0] > k && count[1] > k) {
21                endIndices[i] = j;
22                count[s[i++] - '0']--;
23            }
24          
25            // Update prefix sum, where prefixSum[j + 1] indicates sum up to index j
26            prefixSum[j + 1] = prefixSum[j] + j - i + 1;
27        }
28      
29        // Vector to store the results of the queries
30        vector<long long> results;
31      
32        // Process each query
33        for (const auto& query : queries) {
34            int left = query[0], right = query[1];
35          
36            // Find the smallest possible end for the valid substring starting at 'left'
37            int p = min(right + 1, endIndices[left]);
38          
39            // Calculate sum for substring starting inside a single window
40            long long leftSubstring = (1LL + p - left) * (p - left) / 2;
41          
42            // Calculate remaining sum using pre-calculated prefix sum
43            long long remainingSubstring = prefixSum[right + 1] - prefixSum[p];
44          
45            // Store the total sum for current query
46            results.push_back(leftSubstring + remainingSubstring);
47        }
48      
49        return results;
50    }
51};
52
1function countKConstraintSubstrings(s: string, k: number, queries: number[][]): number[] {
2    // Array to count number of '0's and '1's in current window
3    const count: [number, number] = [0, 0];
4    // Length of the string
5    const lengthOfString = s.length;
6    // Array to store the rightmost boundary where the condition is valid
7    const maxIndex: number[] = Array(lengthOfString).fill(lengthOfString);
8    // Prefix sum array to help in calculating number of valid substrings
9    const prefixSum: number[] = Array(lengthOfString + 1).fill(0);
10
11    // Start and end indices of the current window
12    let start = 0;
13  
14    // Iterate through the string
15    for (let end = 0; end < lengthOfString; ++end) {
16        // Increment count of current character
17        count[+s[end]]++;
18
19        // Adjust the start of the window if min count of '0's and '1's exceeds k
20        while (Math.min(count[0], count[1]) > k) {
21            maxIndex[start] = end;    // Mark current end position
22            count[+s[start++]]--;     // Slide the window right
23        }
24
25        // Update prefix sum, denoting valid substrings count up to current end
26        prefixSum[end + 1] = prefixSum[end] + end - start + 1;
27    }
28
29    // Array to store results for each query
30    const results: number[] = [];
31
32    // Process each query
33    for (const [left, right] of queries) {
34        // Find minimum between end boundary (right+1) or max valid index for current start
35        const p = Math.min(right + 1, maxIndex[left]);
36      
37        // Calculate number of valid substrings using arithmetic series formula for the range [left, p)
38        const validSubstringCountInRange = ((1 + p - left) * (p - left)) / 2;
39      
40        // Calculate additional valid substrings using the prefix sum array
41        const additionalSubstrings = prefixSum[right + 1] - prefixSum[p];
42      
43        // Total valid substrings within query bounds
44        results.push(validSubstringCountInRange + additionalSubstrings);
45    }
46
47    return results;
48}
49

Time and Space Complexity

The time complexity of the code is O(n + m), where n is the length of the string s and m is the number of queries. This arises because the algorithm iterates through the string s once to calculate the prefix sums and process character counts, which takes O(n) time. Additionally, it processes each query individually, contributing a total of O(m) to the complexity.

The space complexity of the code is O(n), due to the storage requirements for the arrays d and pre, each of which stores information proportional to the length of the string s.

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:
Question 1 out of 10

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More