Longest Uniform Answer Run

Medium

The answer key of a true/false quiz is the string answers: 'T' means true and 'F' means false. The quiz author wants the key to contain as long a run of identical answers in a row as possible, whether T or F. They may change at most flips answers in the key (any answer can be switched to the opposite one). Return the length of the longest run of identical characters that can be obtained.

Example 1

answers="TFTTFT", flips=1 → 4

Flip the F at index 1 to get TTTTFT: four Ts in a row. Five equal answers in a row cannot be made with one change.

Example 2

answers="FFTF", flips=2 → 4

One change is enough: turning the T into F gives FFFF.

Constraints

1 ≤ len(answers) ≤ 5·10⁴
answers consists only of 'T' and 'F'
1 ≤ flips ≤ len(answers)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Binary Search Prefix Sum Sliding Window

Similar problems

Matching Stretch Within Budget Medium Few Zeros or Few Ones: Range Queries Hard Shortest Stretch to the Goal Medium Windows With a Small Product Medium Longest Run of Ones With k Fixes Medium

Input

answers="TFTTFT", flips=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 135 tests on the server, hidden ones included.