Watch 9 video solutions for Swap For Longest Repeated Character Substring, a medium level problem involving Hash Table, String, Sliding Window. This walkthrough by leetuition has 7,801 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: Given a string, you may swap any two characters once. The goal is to maximize the length of a substring containing only one repeating character. The trick is recognizing that you can extend runs of the same character by borrowing one identical character from elsewhere in the string.
Approach 1: Group Counting and Swap (O(n) time, O(1) space)
Count the frequency of each character first using a small array or hash table. Then scan the string and identify contiguous groups of the same character. For each group of length k, check if the total frequency of that character is greater than k; if so, you can extend the group by one through a swap. This works because one extra matching character must exist elsewhere in the string. This approach is simple and efficient when analyzing repeated blocks directly.
Approach 2: Segmentation and Swap Strategy (O(n) time, O(1) space)
Break the string into segments of identical characters such as aaa, b, aaa. Store these segments as pairs of (character, length). If two segments of the same character are separated by exactly one different character, they can potentially merge through a swap. For example, aaa b aaa can become length 6 if another a exists elsewhere. Iterate through the segments, compute the merged length, and cap it by the total frequency of that character. This segment-based reasoning avoids checking every substring and works well for string problems with repeating patterns.
Approach 3: Sliding Window with Frequency Count (O(n) time, O(1) space)
Use a sliding window to maintain a window where most characters match the dominant character. Track the frequency of characters in the window and allow at most one mismatch that could be fixed by a swap. Expand the right pointer while the window remains valid, and shrink from the left when violations occur. The maximum window length corresponds to the longest substring that can become uniform with one swap. This technique generalizes well and mirrors patterns used in many interview problems involving longest substrings.
Recommended for interviews: The segmentation strategy is typically the clearest and easiest to reason about during interviews. It directly models how swaps merge character blocks and stays linear in time. Mentioning the group-count idea shows understanding of character frequency constraints, while implementing the optimal O(n) segmentation or sliding window approach demonstrates strong string problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Group Counting and Swap | O(n) | O(1) | When analyzing contiguous character groups and simple frequency checks |
| Segmentation and Swap Strategy | O(n) | O(1) | Best general approach; handles separated segments like "aaa b aaa" cleanly |
| Sliding Window with Frequency Count | O(n) | O(1) | Useful when extending substring window logic used in many longest substring problems |