One-Color Run After Repaints

Medium

A path is laid with tiles whose colors are written as the string tiles: each uppercase English letter stands for one color. You may repaint at most repaints tiles, each in any of the 26 colors. Return the greatest length of a run of consecutive tiles of a single color that you can get after repainting.

Example 1

tiles="RRGRBRR", repaints=1 → 4

Repaint the G red to get RRRRBRR: the first four tiles now share one color.

Example 2

tiles="ABCD", repaints=0 → 1

No repaints are allowed, and no two neighboring tiles match.

Example 3

tiles="XYXY", repaints=2 → 4

Repaint both Y tiles to X and the whole path is one color.

Constraints

1 ≤ len(tiles) ≤ 10⁵
0 ≤ repaints ≤ len(tiles)
tiles consists of uppercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Sliding Window

Similar problems

Longest Repeat-Free Stretch Medium Two-Letter Stretch Medium Recurring Gene Windows Medium Window with Few Kinds of Letters Medium Every Letter at Least k Times Medium

Input

tiles="RRGRBRR", repaints=1

Expected

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