Smallest Substring With Identical Characters II

Smallest Substring With Identical Characters II - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "1110", numOps = 1

› Output: 1

💡 Note: We can flip s[1] to get "1010". The longest identical substring is now "1" with length 1, which is the minimum possible.

Example 2 — Multiple Operations

$ Input: s = "000111", numOps = 2

› Output: 2

💡 Note: We can flip positions 1 and 4 to get "010101". Now the longest identical substring has length 1. Or flip position 2 to get "001111" then position 5 to get "001110", giving max length 2.

Example 3 — No Operations Needed

$ Input: s = "101", numOps = 1

› Output: 1

💡 Note: The string already has max identical substring length 1, so no operations are needed.

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of '0' and '1'
0 ≤ numOps ≤ s.length

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string with allowed flips

Process

Find optimal flips to minimize max identical length

Output

Minimum possible max identical substring length

Key Takeaway

🎯 Key Insight: Binary search on the answer - if we can achieve max length k, we can achieve any length > k

Asked in

G Google 15 f Meta 12 a Amazon 8 M Microsoft 6

The key insight is to use binary search on the answer space. If we can achieve a maximum identical substring length of k, we can also achieve any length > k. The optimal approach uses binary search with sliding window validation to check if each candidate answer is achievable within the operation limit. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(n log n)	O(1)	Binary search the minimum possible max length, validate with sliding window
Brute Force	O(2^numOps × n)	O(n)	Try all possible combinations of at most numOps flips

Binary Search on Answer — Algorithm Steps

Binary search on answer: left=1, right=n
For each mid value, check if we can achieve max length ≤ mid
Use sliding window: for each possible max length, find minimum flips needed
If achievable with ≤ numOps flips, try smaller answer; otherwise try larger

Visualization

Tap to expand

Step-by-Step Walkthrough

Binary Search Setup

Search space [1, n] for minimum achievable max length

Validation

For each candidate, check if achievable with ≤ numOps flips

Convergence

Narrow down to optimal answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canAchieve(char* s, int numOps, int maxLen) {
    int n = strlen(s);
    
    // Try alternating patterns
    char patterns[2][3] = {"01", "10"};
    
    for (int p = 0; p < 2; p++) {
        int flips = 0;
        for (int i = 0; i < n; i++) {
            char expected = patterns[p][i % 2];
            if (s[i] != expected) {
                flips++;
            }
        }
        
        if (flips <= numOps) {
            // Check if this pattern achieves maxLen
            int currentLen = 1;
            int maxIdentical = 1;
            for (int i = 1; i < n; i++) {
                char expectedPrev = patterns[p][(i-1) % 2];
                char expectedCurr = patterns[p][i % 2];
                if (expectedCurr == expectedPrev) {
                    currentLen++;
                    if (currentLen > maxIdentical) {
                        maxIdentical = currentLen;
                    }
                } else {
                    currentLen = 1;
                }
            }
            if (maxIdentical <= maxLen) {
                return 1;
            }
        }
    }
    
    // Try breaking runs approach
    for (int targetLen = 1; targetLen <= maxLen; targetLen++) {
        int flipsUsed = 0;
        
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s[j] == s[i]) {
                j++;
            }
            int runLength = j - i;
            
            if (runLength > targetLen) {
                int flipsNeeded = runLength / (targetLen + 1);
                flipsUsed += flipsNeeded;
            }
            
            i = j;
        }
        
        if (flipsUsed <= numOps) {
            return 1;
        }
    }
    
    return 0;
}

int solution(char* s, int numOps) {
    int n = strlen(s);
    
    int left = 1, right = n;
    int result = n;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canAchieve(s, numOps, mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

int main() {
    char s[1001];
    int numOps;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    scanf("%d", &numOps);
    
    printf("%d\n", solution(s, numOps));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Binary search O(log n) iterations, each validation takes O(n) sliding window

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for binary search and sliding window

✓ Linear Space

15.4K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler