#3258

Easy

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Count Substrings That Satisfy K-Constraint I

Count all substrings in a binary string that meet a given k-constraint using an efficient sliding window approach.

Problem Statement

You are given a binary string s and an integer k. A substring of s satisfies the k-constraint if it meets specific conditions based on the number of consecutive 0s or 1s.

Return the total number of substrings of s that satisfy the k-constraint. Constraints: 1 <= s.length <= 50, 1 <= k <= s.length, s contains only '0' and '1'.

Examples

Example 1

Input: s = "10101", k = 1

Output: 12

Every substring of s except the substrings "1010" , "10101" , and "0101" satisfies the k-constraint.

Example 2

Input: s = "1010101", k = 2

Output: 25

Every substring of s except the substrings with a length greater than 5 satisfies the k-constraint.

Example 3

Input: s = "11111", k = 1

Output: 15

All substrings of s satisfy the k-constraint.

Constraints

1 <= s.length <= 50
1 <= k <= s.length
s[i] is either '0' or '1'.

Solution Approach

Sliding Window with Running Counts

Maintain a window of characters and track counts of consecutive 0s and 1s. Expand the window and update counts, checking if the substring satisfies the k-constraint before adding to the total.

Incremental Substring Validation

Instead of recomputing for every substring, incrementally check each new character added to the window and adjust the state to determine if the substring remains valid.

Brute Force for Small Strings

For short strings, iterate through all possible substrings and validate each one directly against the k-constraint. Useful for initial understanding or verifying the sliding window implementation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n^2) for brute force to O(n) for optimized sliding window with running state updates. Space complexity is O(1) for counters or O(n) if storing all valid substrings.

What Interviewers Usually Probe

Do you notice a pattern where counting substrings can be done without full recomputation?
Can you maintain a dynamic state as you expand the substring window?
Consider what happens when k is equal to the length of s or 1.

Common Pitfalls or Variants

Common pitfalls

Failing to update counts correctly when the window slides, leading to double-counting.
Using brute force on longer strings can exceed time limits even though constraints are small.
Misinterpreting the k-constraint for consecutive 0s or 1s.

Follow-up variants

Count substrings where the number of 1s minus 0s does not exceed k.
Find the longest substring satisfying the k-constraint instead of counting all.
Apply the k-constraint to ternary strings instead of binary strings.

FAQ

What is the main pattern used to solve Count Substrings That Satisfy K-Constraint I?

The problem primarily uses a sliding window with running state updates to efficiently count valid substrings.

Can brute force solve this problem within constraints?

Yes, because the string length is up to 50, but sliding window is more efficient and avoids repeated computation.

How do you update state when the window slides?

Track consecutive 0s and 1s dynamically, incrementing or decrementing counts as characters enter or leave the window.

What happens if k equals the string length?

All substrings automatically satisfy the k-constraint, simplifying the counting to total substrings.

Are there common mistakes when implementing this sliding window?

Yes, such as miscounting overlapping substrings, forgetting to update consecutive counts, or off-by-one errors in the window boundaries.

terminal

Solution

Solution 1: Sliding Window

We use two variables $\textit{cnt0}$ and $\textit{cnt1}$ to record the number of $0$s and $1$s in the current window, respectively. We use $\textit{ans}$ to record the number of substrings that satisfy the $k$ constraint, and $l$ to record the left boundary of the window.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        cnt = [0, 0]
        ans = l = 0
        for r, x in enumerate(map(int, s)):
            cnt[x] += 1
            while cnt[0] > k and cnt[1] > k:
                cnt[int(s[l])] -= 1
                l += 1
            ans += r - l + 1
        return ans

Continue Practicing

#3261 count substrings that satisfy k constraint ii #3234 count the number of substrings with dominant ones #3297 count substrings that can be rearranged to contain a string i