Skip to main content

Longest Non-Repeating Segment Expander

hard
StringSliding WindowTwo PointersSliding Window
Asked atGoogleAmazonMetaMicrosoftUber

Problem Description

Given a string `text` and an integer `budget`, you may replace **at most `budget`** characters in any contiguous substring with any character you like. After these replacements, find the length of the longest substring that consists of all the same character.

In other words, choose a contiguous segment of `text`, make up to `budget` character swaps inside it, and maximize the length of the resulting uniform segment.

**Example 1:**
```
Input: text = "PPQPPQPP", budget = 2
Output: 6
Explanation: Replace the two 'Q's in the middle to get "PPPPPPPP" — no wait, with budget=2 we can replace indices 2,5 (both 'Q') giving "PPPPPPPP" ... but that's length 8. Let me restate:
Actually "PPQPPQPP": replacing the two Q's (positions 2 and 5) with 'P' gives "PPPPPPPP", length 8.
```

Let me provide cleaner examples:

**Example 1:**
```
Input: text = "AABABBA", budget = 1
Output: 4
Explanation: Replace one 'B' in "ABAB" window to get "AAAB" (length 4), or "BABB"→"BABB"... the optimal is window "ABAB" → replace one → "AABB" or "ABAA" which isn't all same. Actually the window "BABB" with 1 replacement → "BBBB" = length 4. So answer is 4.
```

**Example 2:**
```
Input: text = "GXGXG", budget = 2
Output: 5
Explanation: Replace the two 'X's with 'G' → "GGGGG", length 5.
```

Constraints

  • 1 <= text.length <= 10^5
  • 0 <= budget <= text.length
  • text consists of uppercase English letters only

Follow-up

Generalise to allow lowercase and uppercase English letters (52 distinct chars) and solve in O(n) time.

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.