We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Substring With Identical Characters II

Number: 3706

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a binary string s and an integer numOps, you are allowed to flip (change 0 to 1 or 1 to 0) at most numOps characters. After these operations the “score” of the string is measured by the length of its longest contiguous substring that consists of identical characters. The goal is to choose the flips so that this longest “identical‐characters” substring is as short as possible – and to return that minimum possible length.

Key Insights

  • The final string t (after performing flips) is completely under our control as long as we incur the cost (flip count) when t[i] ≠ s[i].
  • A necessary condition for t to be “good” is that every contiguous segment (or “run”) of identical characters in t has length at most M (a candidate answer).
  • Because t is binary and any two adjacent blocks must be different, one may think of t as constructed by “block segmentation” where we choose breakpoints by flipping selected characters.
  • For an isolated run in the original s (i.e. a maximal block of identical characters), if we decide to “break” it by flipping some of its characters, then the unflipped positions will appear in one or more segments. Importantly, if we flip k characters within a run of length L, then the run’s unflipped “pieces” (at most k+1) must each have length ≤ M.
  • A bit of algebra shows that for a run of length L, the minimum number k of flips needed so that each unflipped segment is of length at most M satisfies: (k+1)×M ≥ L – k. Solving for k yields k ≥ (L – M)/(M+1). In other words, the minimal flips needed for that run is ceil((L – M)/(M+1)) (and 0 if L ≤ M).
  • By “simulating” this idea over all runs in s (the runs are by definition separated by a change in character) we can compute, for a given candidate M, the total number of flips required.
  • Then a binary search over possible M (from 1 to the length of the longest run in s) lets us find the smallest M such that the total cost does not exceed numOps.

Space and Time Complexity

Time Complexity: O(n · log(maxRun)) where n is the length of the string and maxRun is the length of the longest contiguous block in s. Space Complexity: O(n) for storing the run-lengths (in practice the run array is much shorter than n).

Solution

The main idea is to “guess” an answer M (the maximum allowed length for any identical‐character substring in the final string). For each contiguous block (run) in the original string, if its length L is more than M, then even if we flip some of its characters to break it up, we must ensure every unflipped piece has length ≤ M. With k flips in that block, the unflipped characters (L – k in number) will form at most k+1 pieces; so we require (k+1)*M ≥ L – k. The minimal k satisfying this is k = ceil((L – M)/(M+1)). (Note that if L ≤ M, no flip is needed.)
Summing this minimal cost over the runs gives the total flips needed to “fix” s so that no contiguous segment is longer than M. Then by binary searching on M we can pick the minimum M for which the total cost is ≤ numOps.

Key implementation points include: • Preprocessing s to compute an array of run lengths. • For each candidate M (1 ≤ M ≤ maxRun) using the formula k = ceil((L – M)/(M+1)) (which can be computed by integer arithmetic as: cost = (L // (M+1)) when L > M; note that when L ≤ M this cost is 0). • Using binary search (the check function runs in O(n) over the runs) to find the smallest M that is “achievable” with ≤ numOps flips.

Code Solutions

# Python solution with detailed comments
def smallestSubstringLength(s: str, numOps: int) -> int:
    n = len(s)
    # Build an array of (char, length) for each contiguous run in s.
    runs = []
    count = 1
    for i in range(1, n):
        if s[i] == s[i-1]:
            count += 1
        else:
            runs.append(count)
            count = 1
    runs.append(count)  # append the last run

    # The answer must be between 1 and the length of the longest run.
    lo, hi = 1, max(runs)
    ans = hi

    while lo <= hi:
        mid = (lo + hi) // 2  # candidate maximum block length allowed
        total_flips = 0
        # For each run, compute required flips if run length L > mid.
        for L in runs:
            if L > mid:
                # minimal k such that (k+1)*mid >= L - k
                # k = ceil((L - mid) / (mid + 1))
                # We can compute this with integer arithmetic:
                # if (L - mid) % (mid + 1) == 0 then k = (L - mid) // (mid + 1) else add 1.
                required = (L - mid + mid) // (mid + 1)
                # The above expression simplifies to L // (mid + 1).
                total_flips += L // (mid + 1)
        # If the total flips needed is within numOps, candidate mid is feasible.
        if total_flips <= numOps:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

# Example usage:
print(smallestSubstringLength("000001", 1))  # Expected output: 2
print(smallestSubstringLength("0000", 2))    # Expected output: 1
print(smallestSubstringLength("0101", 0))    # Expected output: 1
← Back to All Questions