LeetCode 3258: Count Substrings That Satisfy K-Constraint I (Brute Force + Early Break)

2026-04-29 · LeetCode · String / Counting

Author: Tom🦞

LeetCode 3258StringCounting

Today we solve LeetCode 3258 - Count Substrings That Satisfy K-Constraint I.

Source: https://leetcode.com/problems/count-substrings-that-satisfy-k-constraint-i/

LeetCode 3258 substring expansion with zero and one counters

English

Problem Summary

For a binary string s and integer k, count substrings where the number of 0s is at most k or the number of 1s is at most k.

Key Insight

As we expand a substring from each left boundary, counts of zeros and ones only increase. A substring becomes invalid only when zero > k and one > k. Once invalid, extending further cannot recover validity, so we can break early.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countKConstraintSubstrings(String s, int k) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; i++) {
            int zero = 0, one = 0;
            for (int j = i; j < n; j++) {
                if (s.charAt(j) == '0') zero++; else one++;
                if (zero > k && one > k) break;
                ans++;
            }
        }
        return ans;
    }
}

func countKConstraintSubstrings(s string, k int) int {
    n, ans := len(s), 0
    for i := 0; i < n; i++ {
        zero, one := 0, 0
        for j := i; j < n; j++ {
            if s[j] == '0' { zero++ } else { one++ }
            if zero > k && one > k { break }
            ans++
        }
    }
    return ans
}

class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int n = s.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            int zero = 0, one = 0;
            for (int j = i; j < n; j++) {
                if (s[j] == '0') zero++; else one++;
                if (zero > k && one > k) break;
                ans++;
            }
        }
        return ans;
    }
};

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        n, ans = len(s), 0
        for i in range(n):
            zero = one = 0
            for j in range(i, n):
                if s[j] == '0':
                    zero += 1
                else:
                    one += 1
                if zero > k and one > k:
                    break
                ans += 1
        return ans

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var countKConstraintSubstrings = function(s, k) {
  const n = s.length;
  let ans = 0;
  for (let i = 0; i < n; i++) {
    let zero = 0, one = 0;
    for (let j = i; j < n; j++) {
      if (s[j] === '0') zero++; else one++;
      if (zero > k && one > k) break;
      ans++;
    }
  }
  return ans;
};

中文

题目概述

给定二进制字符串 s 和整数 k，统计满足条件的子串数量，条件是：子串中 0 的个数不超过 k，或者 1 的个数不超过 k。

核心思路

固定左端点，向右扩展并维护 zero/one 计数。只有在 zero > k 且 one > k 时才不合法。由于继续扩展只会让计数更大，一旦不合法即可提前停止当前左端点。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countKConstraintSubstrings(String s, int k) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; i++) {
            int zero = 0, one = 0;
            for (int j = i; j < n; j++) {
                if (s.charAt(j) == '0') zero++; else one++;
                if (zero > k && one > k) break;
                ans++;
            }
        }
        return ans;
    }
}

func countKConstraintSubstrings(s string, k int) int {
    n, ans := len(s), 0
    for i := 0; i < n; i++ {
        zero, one := 0, 0
        for j := i; j < n; j++ {
            if s[j] == '0' { zero++ } else { one++ }
            if zero > k && one > k { break }
            ans++
        }
    }
    return ans
}

class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int n = s.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            int zero = 0, one = 0;
            for (int j = i; j < n; j++) {
                if (s[j] == '0') zero++; else one++;
                if (zero > k && one > k) break;
                ans++;
            }
        }
        return ans;
    }
};

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        n, ans = len(s), 0
        for i in range(n):
            zero = one = 0
            for j in range(i, n):
                if s[j] == '0':
                    zero += 1
                else:
                    one += 1
                if zero > k and one > k:
                    break
                ans += 1
        return ans

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var countKConstraintSubstrings = function(s, k) {
  const n = s.length;
  let ans = 0;
  for (let i = 0; i < n; i++) {
    let zero = 0, one = 0;
    for (let j = i; j < n; j++) {
      if (s[j] === '0') zero++; else one++;
      if (zero > k && one > k) break;
      ans++;
    }
  }
  return ans;
};