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 I

Number: 3690

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a binary string s and an integer numOps, you may flip up to numOps characters (i.e. change a '0' to a '1' or vice versa). The goal is to minimize the length of the longest contiguous substring where all characters are identical. Return that minimum possible length after performing at most numOps flips.

Key Insights

  • We want to ensure that after at most numOps flips, no contiguous sequence of identical characters is longer than some target value L.
  • Flipping a character in the middle of a long contiguous segment can break it into smaller segments.
  • For each candidate L (the maximum allowed run length), we can simulate a greedy left-to-right process: whenever adding a character would exceed L, flip it (which resets the current run to 1) if flips remain.
  • A binary search is used to efficiently determine the smallest L for which the simulation succeeds.
  • This simulation takes O(n) time and the binary search over L takes O(log n) iterations, for an overall O(n log n) time per test case.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(1)

Solution

We use binary search on the answer L (the maximum allowed identical substring length after flips). For each candidate L, a greedy simulation scans through the string. We maintain the current streak (run) of identical characters. If adding the next character would push the run length over L, we flip that character (which resets the run to 1) and decrement our available operations. If at any point the number of flips required exceeds numOps, then candidate L is not achievable. Otherwise, if we can process the entire string, candidate L is valid and we search for a possibly smaller L.

The key data structure is a few integer counters and a character variable for the last processed (or flipped) character. The greedy approach is optimal because any time a run length would exceed L, we are forced to perform a flip so that the run stays at or below L.

Code Solutions

def canAchieve(s, numOps, L):
    # Initialize the number of available flips
    ops = numOps
    # 'prev' holds the last character in the resulting string after flips
    prev = s[0]
    # current run length of identical chars
    run = 1
    # Process from the second character to the end
    for i in range(1, len(s)):
        if s[i] == prev:
            # If appending would exceed allowed run length L
            if run + 1 > L:
                if ops <= 0:
                    return False
                ops -= 1
                # Flip the current character to the opposite of prev
                prev = '1' if prev == '0' else '0'
                run = 1   # reset run length as the flipped char is different
            else:
                run += 1
        else:
            # Different character: simply update previous and reset run length
            prev = s[i]
            run = 1
    return True

def smallestSubstring(s, numOps):
    low, high = 1, len(s)
    ans = high
    while low <= high:
        mid = (low + high) // 2
        if canAchieve(s, numOps, mid):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    return ans

# Example usage:
s = "000001"
numOps = 1
print(smallestSubstring(s, numOps))  # Expected output: 2
← Back to All Questions