Scale Engineer

Smallest Substring With Identical Characters I

Hard
#3019Time: O(n^2). The outer loop runs up to `n` times. Inside the loop, the `isPossible` check function takes `O(n)` time to scan the string.Space: O(1). We only use a few variables to keep track of counts and loop indices.
Patterns
Enumeration
Algorithms
Binary Search
Data structures
Array

Prompt

You are given a binary string s of length n and an integer numOps.

You are allowed to perform the following operation on s at most numOps times:

  • Select any index i (where 0 <= i < n) and flip s[i]. If s[i] == '1', change s[i] to '0' and vice versa.

You need to minimize the length of the longest substring of s such that all the characters in the substring are identical.

Return the minimum length after the operations.

 

Example 1:

Input: s = "000001", numOps = 1

Output: 2

Explanation: 

By changing s[2] to '1', s becomes "001001". The longest substrings with identical characters are s[0..1] and s[3..4].

Example 2:

Input: s = "0000", numOps = 2

Output: 1

Explanation: 

By changing s[0] and s[2] to '1', s becomes "1010".

Example 3:

Input: s = "0101", numOps = 0

Output: 1

 

Constraints:

  • 1 <= n == s.length <= 1000
  • s consists only of '0' and '1'.
  • 0 <= numOps <= n

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible answer for the minimum length, from 1 up to n. For each potential length k, we calculate the minimum number of flips required to ensure no substring of identical characters is longer than k. The first value of k that can be achieved with at most numOps flips is our answer.

Algorithm

  • Loop through k from 1 to n. k represents the potential maximum length of an identical character substring.
  • Inside the loop, calculate the total flips needed, requiredFlips, to satisfy the length constraint k.
  • To calculate requiredFlips:
    • Initialize requiredFlips = 0.
    • Iterate through the string s to find all contiguous runs of '0's. For each run of length len, if len > k, add len / (k + 1) to requiredFlips.
    • Iterate through the string s again to find all contiguous runs of '1's. For each run of length len, if len > k, add len / (k + 1) to requiredFlips.
  • If requiredFlips <= numOps, it means we can achieve a maximum run length of k. Since we are iterating k from 1 upwards, this is the smallest possible length. Return k.

Walkthrough

The core idea is to test each possible length k starting from 1. Since we are looking for the minimum length, the first k that satisfies the condition will be the answer.

To check if a length k is achievable, we need to calculate the minimum number of operations. This involves breaking up any run of identical characters (both '0's and '1's) that is longer than k.

For a run of identical characters of length len > k, we need to introduce flips to break it into segments of length at most k. The most efficient way to do this is to place a flip at every (k+1)-th position. The number of flips required for this single run is floor(len / (k + 1)).

We calculate the total flips needed by summing up the flips required for all runs of '0's longer than k and all runs of '1's longer than k.

We iterate k from 1 to n. For each k, we compute this total required flips. If it's less than or equal to numOps, we've found our minimal length, and we can return k.

class Solution {    public int smallestSubstring(String s, int numOps) {        int n = s.length();        for (int k = 1; k <= n; k++) {            if (isPossible(s, numOps, k)) {                return k;            }        }        return n; // Should not be reached given the problem constraints    }     private int countFlipsForChar(String s, int k, char targetChar) {        int flips = 0;        int currentRun = 0;        for (int i = 0; i < s.length(); i++) {            if (s.charAt(i) == targetChar) {                currentRun++;            } else {                if (currentRun > k) {                    flips += currentRun / (k + 1);                }                currentRun = 0;            }        }        if (currentRun > k) {            flips += currentRun / (k + 1);        }        return flips;    }     private boolean isPossible(String s, int numOps, int k) {        int requiredFlips = countFlipsForChar(s, k, '0') + countFlipsForChar(s, k, '1');        return requiredFlips <= numOps;    }}

Complexity

Time

O(n^2). The outer loop runs up to `n` times. Inside the loop, the `isPossible` check function takes `O(n)` time to scan the string.

Space

O(1). We only use a few variables to keep track of counts and loop indices.

Trade-offs

Pros

  • Simple and straightforward to understand and implement.

  • Correctly solves the problem for smaller constraints.

Cons

  • Inefficient due to the nested loop structure, leading to a quadratic time complexity.

  • For large n, this approach can be too slow and may result in a 'Time Limit Exceeded' error on some platforms.

Solutions

class Solution {private  char[] s;private  int numOps;public  int minLength(String s, int numOps) {    this.numOps = numOps;    this.s = s.toCharArray();    int l = 1, r = s.length();    while (l < r) {      int mid = (l + r) >> 1;      if (check(mid)) {        r = mid;      } else {        l = mid + 1;      }    }    return l;  }private  boolean check(int m) {    int cnt = 0;    if (m == 1) {      char[] t = {'0', '1'};      for (int i = 0; i < s.length; ++i) {        if (s[i] == t[i & 1]) {          ++cnt;        }      }      cnt = Math.min(cnt, s.length - cnt);    } else {      int k = 0;      for (int i = 0; i < s.length; ++i) {        ++k;        if (i == s.length - 1 || s[i] != s[i + 1]) {          cnt += k / (m + 1);          k = 0;        }      }    }    return cnt <= numOps;  }}

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