Longest Non-Repeating Segment Expander
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.