Skip to main content
Talentd

Smallest Substring With Identical Characters II - Solution & Explanation

HardStringBinary Search5 min readAsked at: Salesforce
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 <= 105
  • s consists only of '0' and '1'.
  • 0 <= numOps <= n

Approach Overview

Problem Overview: You are given a string and a limited number of modification operations. The goal is to minimize the length of the longest substring consisting of identical characters after applying at most k changes. The result is the smallest possible maximum run length achievable with those operations.

Approach 1: Linear Search on Maximum Run Length (Brute Force) (Time: O(n^2), Space: O(1))

Start by computing runs of identical characters in the string. Try every possible maximum allowed run length L from 1 to n. For each candidate L, iterate through all runs and calculate how many characters must be changed to break that run so no segment exceeds L. A run of length r requires roughly r / (L + 1) modifications because each modification splits the run. If the total required operations stay within k, the value is feasible. This approach is straightforward but too slow for large inputs because it checks every possible length.

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

The key observation: if a maximum run length L is achievable, then any value larger than L is also achievable. This monotonic property makes the problem ideal for binary search. Search the smallest feasible L in the range [1, n]. For each midpoint, scan the string and group consecutive identical characters. For a run of length r, compute the number of changes required to ensure each segment length is at most L. Each modification effectively breaks the run, so the required operations are r / (L + 1). Accumulate the operations across all runs and stop early if the count exceeds k.

The feasibility check is linear because it processes each character once while tracking run lengths. Combined with binary search, the total complexity becomes O(n log n), which handles large strings comfortably. The algorithm relies on simple iteration and greedy splitting of runs rather than complex data structures.

Recommended for interviews: Binary search on the answer with a greedy feasibility check is the expected solution. The brute-force attempt shows you understand the relationship between run length and required modifications, but the O(n log n) approach demonstrates strong problem-solving skills using monotonic properties and binary search over the answer space.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Search on Maximum Run LengthO(n^2)O(1)Useful for understanding the relationship between run length and required modifications
Binary Search with Greedy Run SplittingO(n log n)O(1)Optimal solution for large inputs; leverages monotonic property of feasible run lengths

Video Solution

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

Watch 6 more video solutions →

Frequently Asked Questions

Is Smallest Substring With Identical Characters II easy or hard?
Smallest Substring With Identical Characters II is classified as Hard. The difficulty comes from recognizing the monotonic property that allows binary search on the answer and designing a correct greedy check for breaking long runs.
Smallest Substring With Identical Characters II Python/Java solution
Implement binary search on the possible maximum run length. For each candidate value, iterate through the string, compute lengths of consecutive identical characters, and accumulate the number of required modifications using r / (L + 1). This logic translates cleanly to Python, Java, C++, Go, and TypeScript.
How to solve Smallest Substring With Identical Characters II in O(n)?
A strictly O(n) solution is generally not used because the target run length is unknown. Instead, binary search narrows the answer space while a linear scan validates each candidate. Each validation runs in O(n), giving an overall complexity of O(n log n).
What is the best approach for Smallest Substring With Identical Characters II?
The best approach uses binary search on the answer combined with a greedy feasibility check. You guess the maximum allowed run length L and scan the string to count how many modifications are needed to break runs longer than L. If the required operations are ≤ k, the length is feasible. This produces an O(n log n) time and O(1) space solution.
Is Smallest Substring With Identical Characters II asked at Google/Amazon/Meta?
Problems involving binary search on the answer and string run analysis appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that minimize or maximize substring constraints using greedy checks are especially common in senior-level interviews.
What data structure is used in Smallest Substring With Identical Characters II?
The solution mainly relies on string traversal and counting consecutive runs of characters. No complex data structures are required; the algorithm uses counters and binary search over possible answers.
What is the time complexity of Smallest Substring With Identical Characters II?
The optimal solution runs in O(n log n) time. Binary search is performed over the possible run lengths, and each feasibility check scans the string once to evaluate consecutive character runs. Space complexity is O(1) because only counters and indices are used.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring