LeetCode Problem 3258

Difficulty: 🟢 Easy
Topics: String, Sliding Window

Solution

LeetCode 3258 - Count Substrings That Satisfy K-Constraint I

Problem Understanding

The problem gives us a binary string s, meaning the string contains only the characters '0' and '1', along with an integer k.

A substring is considered valid if it satisfies the k-constraint. The constraint is unusual because it uses an OR condition rather than an AND condition:

• The substring contains at most k zeros, or
• The substring contains at most k ones.

A substring only becomes invalid when both counts exceed k. In other words:

• Valid: zeros <= k OR ones <= k
• Invalid: zeros > k AND ones > k

Our task is to count how many substrings of s are valid.

The input size is very small:

• 1 <= s.length <= 50
• 1 <= k <= s.length

Since the maximum length is only 50, even an O(n²) solution is completely acceptable. However, there is still a nice sliding window observation that leads to an optimal linear solution.

Several edge cases are worth noting:

• A string consisting entirely of one character, such as "11111". Every substring will always satisfy the constraint because one of the counts remains zero.
• A very large k, where every substring becomes valid.
• Alternating strings such as "101010...", where both counts grow together and invalid windows appear sooner.
• Very short strings, including length one.
• Substrings that contain more than k zeros and more than k ones simultaneously, which are the only invalid substrings.

Approaches

Brute Force

The most direct solution is to generate every possible substring.

For each starting position, we extend the ending position one character at a time while maintaining counts of zeros and ones. For every substring, we check whether:

zeros <= k OR ones <= k

If the condition holds, we increment the answer.

This approach is correct because it explicitly examines every substring and applies the definition exactly as given.

There are O(n²) substrings, and with running counts each substring can be checked in O(1) time. Therefore the overall complexity is O(n²).

Given n <= 50, this solution is perfectly acceptable.

Optimal Sliding Window

The key observation is that a substring becomes invalid only when:

zeros > k AND ones > k

Suppose we maintain a sliding window [left, right].

As we expand right, we count zeros and ones inside the window.

Whenever both counts exceed k, the window is invalid. We repeatedly move left forward until at least one count becomes <= k again.

After this adjustment, the current window is valid.

An important property now holds:

If the window [left, right] is valid, then every suffix ending at right and starting between left and right is also valid.

Therefore, the number of valid substrings ending at right is:

right - left + 1

Adding this value for every position gives the final answer in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Enumerates every substring and checks the constraint directly
Optimal	O(n)	O(1)	Sliding window maintains the longest valid window ending at each position

Algorithm Walkthrough

Optimal Sliding Window

1. Initialize two pointers, left and right, representing the current window.
2. Maintain two counters:

• zero_count
• one_count

These track the number of zeros and ones inside the current window. 3. Iterate right from 0 to n - 1. 4. Add s[right] into the window and update the appropriate counter. 5. Check whether the window is invalid. A window is invalid only when:

zero_count > k AND one_count > k

6. While the window is invalid, move left forward:

• Remove s[left] from the counts.
• Increment left.
• Continue until the window becomes valid again.

7. Once the window is valid, every substring ending at right and starting anywhere from left through right is valid.
8. Add:

right - left + 1

to the answer. 9. After processing all positions, return the accumulated answer.

Why it works

The sliding window always maintains the smallest valid left boundary for the current right boundary. Any window starting before left would have both zero and one counts exceeding k, making it invalid. Any window starting at or after left is a suffix of a valid window and therefore remains valid. Consequently, right - left + 1 exactly counts all valid substrings ending at right, and summing these values counts every valid substring exactly once.

Python Solution

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        left = 0
        zero_count = 0
        one_count = 0
        answer = 0

        for right, ch in enumerate(s):
            if ch == '0':
                zero_count += 1
            else:
                one_count += 1

            while zero_count > k and one_count > k:
                if s[left] == '0':
                    zero_count -= 1
                else:
                    one_count -= 1
                left += 1

            answer += right - left + 1

        return answer

The implementation follows the sliding window algorithm directly.

The variables zero_count and one_count track the composition of the current window. Each new character is added as the right pointer expands.

Whenever both counts exceed k, the window violates the constraint. The inner while loop removes characters from the left side until at least one count becomes <= k, restoring validity.

After the adjustment, the window [left, right] is valid. Every suffix ending at right is therefore valid, so we add right - left + 1 to the answer.

Because each character enters and leaves the window at most once, the algorithm runs in linear time.

Go Solution

func countKConstraintSubstrings(s string, k int) int {
	left := 0
	zeroCount := 0
	oneCount := 0
	answer := 0

	for right := 0; right < len(s); right++ {
		if s[right] == '0' {
			zeroCount++
		} else {
			oneCount++
		}

		for zeroCount > k && oneCount > k {
			if s[left] == '0' {
				zeroCount--
			} else {
				oneCount--
			}
			left++
		}

		answer += right - left + 1
	}

	return answer
}

The Go implementation mirrors the Python version closely. Since the maximum answer is at most the number of substrings, n * (n + 1) / 2, and n <= 50, the standard int type is more than sufficient. No additional data structures are required, so the space usage remains constant.

Worked Examples

Example 1

Input:

s = "10101"
k = 1

Right	Character	Zeros	Ones	Left After Adjustment	Valid Substrings Added	Total
0	1	0	1	0	1	1
1	0	1	1	0	2	3
2	1	1	2	0	3	6
3	0	2	2	1	3	9
4	1	2	2	2	3	12

Final answer:

12

Example 2

Input:

s = "1010101"
k = 2

Right	Character	Left	Added	Running Total
0	1	0	1	1
1	0	0	2	3
2	1	0	3	6
3	0	0	4	10
4	1	0	5	15
5	0	1	5	20
6	1	2	5	25

Final answer:

25

Example 3

Input:

s = "11111"
k = 1

Since the number of zeros is always 0, every substring automatically satisfies the constraint.

Right	Ones	Added	Total
0	1	1	1
1	2	2	3
2	3	3	6
3	4	4	10
4	5	5	15

Final answer:

15

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character enters and leaves the sliding window at most once
Space	O(1)	Only a few counters and pointers are maintained

The crucial observation is that the left pointer never moves backward. Across the entire algorithm, both pointers traverse the string at most once, giving linear running time. The memory usage remains constant because no auxiliary arrays or hash maps are needed.

Test Cases

sol = Solution()

assert sol.countKConstraintSubstrings("10101", 1) == 12  # example 1
assert sol.countKConstraintSubstrings("1010101", 2) == 25  # example 2
assert sol.countKConstraintSubstrings("11111", 1) == 15  # example 3

assert sol.countKConstraintSubstrings("0", 1) == 1  # single character
assert sol.countKConstraintSubstrings("1", 1) == 1  # single character

assert sol.countKConstraintSubstrings("00", 1) == 3  # all substrings valid
assert sol.countKConstraintSubstrings("11", 1) == 3  # all substrings valid

assert sol.countKConstraintSubstrings("01", 1) == 3  # shortest mixed string
assert sol.countKConstraintSubstrings("010", 1) == 6  # every substring valid

assert sol.countKConstraintSubstrings("0011", 1) == 9  # some invalid substrings
assert sol.countKConstraintSubstrings("0101", 1) == 9  # only full length invalid

assert sol.countKConstraintSubstrings("00000", 2) == 15  # all one character type
assert sol.countKConstraintSubstrings("1010", 4) == 10  # k larger than counts

assert sol.countKConstraintSubstrings("110100", 1) == 14  # mixed pattern

Test Summary

Test	Why
"10101", 1	Official example with several invalid substrings
"1010101", 2	Official alternating pattern example
"11111", 1	Official all ones example
"0", 1	Minimum length string
"1", 1	Minimum length string with opposite digit
"00", 1	All zeros
"11", 1	All ones
"01", 1	Smallest mixed binary string
"010", 1	Every substring remains valid
"0011", 1	Contains invalid windows
"0101", 1	Only the longest substring is invalid
"00000", 2	Single character type, larger length
"1010", 4	Large k, all substrings valid
"110100", 1	General mixed stress case

Edge Cases

String Consisting of Only One Character Type

Consider inputs such as "00000" or "11111". One of the character counts always remains zero. Since zero is always less than or equal to k, every substring automatically satisfies the constraint. A buggy implementation might mistakenly require both counts to be within the limit, but the problem uses an OR condition. The sliding window correctly handles this because the invalid condition requires both counts to exceed k.

Very Large k

When k is at least as large as every possible zero count or one count in the string, no substring can ever become invalid. The inner shrinking loop never executes, and the algorithm simply counts all substrings. This produces the expected result of n * (n + 1) / 2.

Alternating Strings

Strings such as "101010101" are the most likely to produce windows where both counts grow together. This is where invalid substrings first appear. The sliding window handles this naturally by shrinking only when both counts exceed k, ensuring that valid windows are preserved while invalid ones are excluded.

Minimum Length Input

When s contains only one character, there is exactly one substring. The algorithm processes a single iteration, adds 1 to the answer, and returns the correct result without any special-case logic.

Windows That Become Invalid

A common bug is shrinking the window when either count exceeds k. The problem requires shrinking only when both counts exceed k. For example, with k = 1, the substring "111" has three ones but zero zeros, so it is still valid. The condition:

while zero_count > k and one_count > k:

correctly captures the exact definition of an invalid substring.