Scale Engineer

Count Substrings That Satisfy K-Constraint I

Easy
#2892Time: O(N^3). There are O(N^2) substrings. For each substring, which has an average length of O(N), we iterate through it to count characters. This results in a total time complexity of O(N^2 * N) = O(N^3).Space: O(N). In each iteration, a new substring of length up to N can be created, requiring O(N) space. The exact space usage depends on the Java implementation of `substring`.
Patterns
Sliding Window
Data structures
String

Prompt

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

A binary string satisfies the k-constraint if either of the following conditions holds:

  • The number of 0's in the string is at most k.
  • The number of 1's in the string is at most k.

Return an integer denoting the number of substrings of s that satisfy the k-constraint.

 

Example 1:

Input: s = "10101", k = 1

Output: 12

Explanation:

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

Example 2:

Input: s = "1010101", k = 2

Output: 25

Explanation:

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

Explanation:

All substrings of s satisfy the k-constraint.

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most straightforward and naive approach. The idea is to systematically generate every possible substring of the input string s. For each generated substring, we then perform a check to see if it satisfies the k-constraint. This check involves counting the number of '0's and '1's within that specific substring and comparing them against k.

Algorithm

  • Initialize a counter validSubstrings to 0.
  • Use a nested loop to generate all substrings. The outer loop i runs from 0 to n-1 (start index), and the inner loop j runs from i to n-1 (end index).
  • For each pair (i, j), extract the substring sub = s.substring(i, j + 1).
  • Count the number of '0's (zeros) and '1's (ones) in sub by iterating through it.
  • If zeros <= k or ones <= k, increment validSubstrings.
  • After checking all substrings, return validSubstrings.

Walkthrough

The implementation involves two nested loops to define the start and end points of all substrings. The outer loop, with index i, determines the starting character of the substring. The inner loop, with index j, determines the ending character. This generates all N * (N + 1) / 2 substrings. For each substring, a third loop (or a similar character-by-character scan) is used to count the occurrences of '0's and '1's. If the count of '0's is at most k, or the count of '1's is at most k, we increment a total counter. This method is easy to conceptualize but performs a lot of repetitive work.

class Solution {    public int countKConstraintSubstrings(String s, int k) {        int n = s.length();        int count = 0;        for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                // Extract the substring                String sub = s.substring(i, j + 1);                int zeros = 0;                int ones = 0;                // Count 0s and 1s in the substring                for (char c : sub.toCharArray()) {                    if (c == '0') {                        zeros++;                    } else {                        ones++;                    }                }                // Check the k-constraint                if (zeros <= k || ones <= k) {                    count++;                }            }        }        return count;    }}

Complexity

Time

O(N^3). There are O(N^2) substrings. For each substring, which has an average length of O(N), we iterate through it to count characters. This results in a total time complexity of O(N^2 * N) = O(N^3).

Space

O(N). In each iteration, a new substring of length up to N can be created, requiring O(N) space. The exact space usage depends on the Java implementation of `substring`.

Trade-offs

Pros

  • Very simple to understand and implement.

  • Correctly solves the problem.

Cons

  • Highly inefficient due to its cubic time complexity.

  • For each of the O(N^2) substrings, it re-scans the substring, leading to redundant work.

  • Will be too slow for larger values of N, although it passes for the given constraints.

Solutions

class Solution {public  int countKConstraintSubstrings(String s, int k) {    int cnt0 = 0, cnt1 = 0;    int ans = 0, l = 0;    for (int r = 0; r < s.length(); ++r) {      int x = s.charAt(r) - '0';      cnt0 += x ^ 1;      cnt1 += x;      while (cnt0 > k && cnt1 > k) {        int y = s.charAt(l++) - '0';        cnt0 -= y ^ 1;        cnt1 -= y;      }      ans += r - l + 1;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem