You are given a string text. You can swap two of the characters in the text.
Return the length of the longest substring with repeated characters.
Example 1:
Input: text = "ababa" Output: 3 Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa" with length 3.
Example 2:
Input: text = "aaabaaa" Output: 6 Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa" with length 6.
Example 3:
Input: text = "aaaaa" Output: 5 Explanation: No need to swap, longest repeated character substring is "aaaaa" with length is 5.
Constraints:
1 <= text.length <= 2 * 104text consist of lowercase English characters only.In #1156 Swap For Longest Repeated Character Substring, the goal is to maximize the length of a substring containing the same character after performing at most one swap. A common strategy uses a frequency map combined with a sliding window. First, count the total occurrences of each character in the string. Then expand a window while tracking the most frequent character within that window.
The key observation is that a window can contain at most one mismatched character if we intend to swap it with the same character from elsewhere in the string. While expanding the window, ensure that the number of characters different from the dominant one does not exceed what a single swap can fix. If it does, shrink the window from the left.
This approach efficiently evaluates possible segments while respecting the global frequency constraint. Using a sliding window ensures we scan the string only once, resulting in O(n) time complexity with O(1) extra space since the alphabet size is fixed.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Frequency Count | O(n) | O(1) |
| Group Counting / Segment Merge Idea | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
There are two cases: a block of characters, or two blocks of characters between one different character. By keeping a run-length encoded version of the string, we can easily check these cases.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Total frequency ensures we don't extend a window beyond the number of available characters that can be swapped in. Even if the window suggests a longer segment, it cannot exceed the actual total count of that character in the string.
Yes, variations of sliding window and string manipulation problems like this are common in FAANG-style interviews. They test understanding of window optimization, frequency tracking, and edge-case handling.
A hash table or fixed-size frequency array works best to store counts of characters in the string. This allows quick checks of total occurrences and helps control the sliding window conditions efficiently.
The optimal approach uses a sliding window combined with a character frequency count. The window tracks the longest segment that can become uniform with at most one swap, ensuring mismatches stay within the allowed limit.