Count Substrings That Satisfy K-Constraint I - Video Solutions

Problem Overview: You are given a binary string s and an integer k. A substring satisfies the k-constraint if the number of 0s in the substring is at most k or the number of 1s is at most k. The task is to count all substrings that satisfy this rule.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Generate every possible substring and count how many 0s and 1s it contains. Use two nested loops: the outer loop selects the starting index and the inner loop expands the substring one character at a time. Maintain running counts of zeros and ones while expanding the window so you don't recompute counts repeatedly. For each extension, check the condition zeros ≤ k or ones ≤ k; if true, increment the answer. This approach directly simulates the definition of the problem. The time complexity is O(n²) because every substring is examined, while space usage remains O(1). It works well for small strings and helps confirm correctness before optimizing.

Approach 2: Sliding Window / Two Pointers (O(n) time, O(1) space)

A substring becomes invalid only when both counts exceed k. That observation allows a sliding window solution. Maintain two pointers left and right representing the current window, along with counters for zeros and ones. Expand the window by moving right across the string and updating the appropriate counter. If both counters become greater than k, shrink the window by moving left forward and decreasing counts until at least one of them is ≤ k again.

For each position of right, every substring ending at right and starting between left and right is valid. That means you can add right - left + 1 to the answer. Each character enters and leaves the window at most once, giving a linear O(n) time complexity with constant O(1) extra space. This technique is a classic application of the two pointers pattern for substring counting problems on strings.

Recommended for interviews: Interviewers expect the sliding window solution. Starting with brute force shows you understand the problem definition and substring generation. Transitioning to the sliding window demonstrates the key insight: the window is invalid only when both character counts exceed k. Recognizing that property and converting it into a linear two‑pointer scan is the main skill being tested.