Skip to main content
Talentd

Smallest Substring With Identical Characters I - Solution & Explanation

HardArrayBinary SearchEnumeration5 min readAsked at: Salesforce, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You’re given a string and a limited number of character modifications. The goal is to minimize the length of the longest substring consisting of identical characters after performing at most k changes. Instead of directly constructing the final string, treat it as an optimization problem: what is the smallest possible maximum run length you can achieve?

Approach 1: Enumerate Possible Maximum Length (Brute Force) (Time: O(n^2), Space: O(1))

Try every possible maximum substring length L from 1 to n. For each candidate length, scan the string and measure contiguous runs of identical characters. If a run has length r, you must break it so no segment exceeds L. That requires floor(r / (L + 1)) character changes because every L+1 characters you need a modification to split the run. Sum the required changes across all runs and check if the total is ≤ k. This works but testing every L makes it too slow for large inputs.

Approach 2: Binary Search on the Answer (Optimal) (Time: O(n log n), Space: O(1))

The key observation: if a maximum run length L is achievable with ≤ k changes, then any value larger than L is also achievable. This monotonic property allows binary search over the answer range [1, n]. For each midpoint L, perform a single pass through the string and compute how many changes are required to break runs longer than L. The run counting step is simple array/enumeration: iterate through the string, track the current run length, and apply floor(run / (L + 1)) to accumulate needed operations. If the total exceeds k, reduce the search range; otherwise try a smaller L.

This approach converts a difficult string modification problem into a decision problem checked in linear time. Binary search reduces the candidate space quickly, while the run-length calculation keeps each check efficient.

Recommended for interviews: Start by describing the brute-force enumeration to show you understand how modifications break character runs. Then move to binary search on the maximum allowed substring length. Interviewers typically expect the O(n log n) solution because it demonstrates recognizing monotonic constraints and combining run-length enumeration with binary search.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Enumerate Maximum Length (Brute Force)O(n^2)O(1)Useful for understanding how many modifications are needed to break long runs
Binary Search + Run EnumerationO(n log n)O(1)General optimal solution when the answer range is monotonic

Video Solution

3398, 3399. Smallest Substring With Identical Characters I & II | 3398 I | Binary Search | !Greedy • Aryan Mittal • 3,916 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Smallest Substring With Identical Characters I easy or hard?
The problem is labeled Hard because it requires recognizing the monotonic property that enables binary search on the answer. The implementation itself is moderate once you derive the formula for splitting long runs and counting required operations.
Smallest Substring With Identical Characters I Python/Java solution
Implement binary search over the answer and write a helper function that scans the string to count required modifications for a given limit L. The same logic works across Python, Java, C++, Go, and TypeScript because it only uses loops, counters, and integer division.
How to solve Smallest Substring With Identical Characters I in O(n)?
A pure O(n) solution is generally not used because the target maximum substring length is unknown. Instead, binary search narrows the answer range while each check runs in O(n). The combined complexity becomes O(n log n), which is efficient for large inputs.
What is the best approach for Smallest Substring With Identical Characters I?
Binary search on the maximum allowed substring length combined with a linear run-length check. For each candidate length L, count how many character modifications are needed to break runs longer than L using floor(run / (L + 1)). The smallest L that requires at most k changes is the answer. This runs in O(n log n) time and O(1) space.
Is Smallest Substring With Identical Characters I asked at Google/Amazon/Meta?
Problems combining binary search on the answer with string run analysis frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of minimizing the longest repeating segment or splitting runs with limited operations are common interview patterns.
What data structure is used in Smallest Substring With Identical Characters I?
No complex data structure is required. The solution relies on simple string or array traversal to compute run lengths, combined with binary search to optimize the maximum allowed substring length.
What is the time complexity of Smallest Substring With Identical Characters I?
The optimal solution runs in O(n log n) time. Binary search explores the range of possible maximum substring lengths, and each feasibility check scans the string once to compute required modifications. Space complexity is O(1) since only counters and pointers are used.

Ready to solve this problem?

Practice Smallest Substring With Identical Characters I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays