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.

Description Hints 2 Solution Video 26:05

3398. Smallest Substring With Identical Characters I

Hard21.0% acceptance2 companies

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

Asked at 2 companies

Salesforce

Google

Topics

Hints open one at a time

Hint 1

Can we use binary search here?

Hint 2

Use DP for predicate function

26:05

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minLength(self, s: str, numOps: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"000001"
1

Input

"0000"
2

Input

"0101"
0

Your code is saved on this device.Solution