Smallest Substring With Identical Characters I

Smallest Substring With Identical Characters I - 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 = "11100", numOps = 1

› Output: 2

💡 Note: We can flip position 2 (0-indexed) to get "11000". The longest identical substring has length 2 (either "11" or "00").

Example 2 — No Operations Needed

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

› Output: 1

💡 Note: The string already alternates, so the longest identical substring is 1. No operations needed.

Example 3 — All Same Characters

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

› Output: 2

💡 Note: We can flip any position to get something like "1011". The longest identical substring becomes 2.

Constraints

1 ≤ n ≤ 1000
0 ≤ numOps ≤ n
s consists only of '0' and '1'

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string "11100" with 1 operation allowed

Process

Strategically flip bits to break long identical segments

Output

Minimum possible maximum substring length: 2

Key Takeaway

🎯 Key Insight: Use binary search on the answer space to efficiently find the minimum achievable maximum substring length

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use binary search on the answer space. We search for the minimum possible maximum substring length by checking if each candidate length is achievable with the given number of operations. The optimal approach uses binary search with greedy feasibility checking in O(n log n) time.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^n × n)	O(n)	Try all possible ways to flip bits and find minimum longest substring
Binary Search on Answer	O(n log n)	O(1)	Binary search on the maximum substring length and check if achievable

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible flip combinations
For each combination, calculate longest identical substring
Return minimum across all combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible flip combinations

Evaluate

Calculate longest identical substring for each

Minimize

Return the minimum result found

Code -

solution.c — C

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

int longestIdenticalSubstring(const char* s) {
    int len = strlen(s);
    if (len == 0) return 0;
    int maxLen = 1;
    int currentLen = 1;
    for (int i = 1; i < len; i++) {
        if (s[i] == s[i-1]) {
            currentLen++;
            if (currentLen > maxLen) {
                maxLen = currentLen;
            }
        } else {
            currentLen = 1;
        }
    }
    return maxLen;
}

int backtrack(char* s, int pos, int len, int opsLeft) {
    if (pos == len) {
        return longestIdenticalSubstring(s);
    }
    
    // Don't flip current position
    int result = backtrack(s, pos + 1, len, opsLeft);
    
    // Flip current position if we have operations left
    if (opsLeft > 0) {
        s[pos] = s[pos] == '0' ? '1' : '0';
        int newResult = backtrack(s, pos + 1, len, opsLeft - 1);
        if (newResult < result) {
            result = newResult;
        }
        s[pos] = s[pos] == '0' ? '1' : '0';  // backtrack
    }
    
    return result;
}

int solution(char* s, int numOps) {
    return backtrack(s, 0, strlen(s), numOps);
}

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(2^n × n)

2^n possible flip combinations, each taking O(n) time to evaluate

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for current string state and recursion stack

⚡ Linearithmic Space

5.6K Views

Medium Frequency

~35 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

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler