Swap For Longest Repeated Character Substring - Solution & Explanation
Problem Statement
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 * 104textconsist of lowercase English characters only.
Approach Overview
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 1: Group Counting and Swap
This approach involves grouping consecutive characters and considering the effect of a single swap between different character groups. We calculate and store the length of contiguous segments of the same character and try to maximize the length by swapping a character from another segment.
The Python code leverages the Counter to first count how many times each character appears, creating groups that record the contiguous sequence of characters. For each group, it attempts to maximize the length by considering adding characters from external parts using the character count.
Code
Python
JavaScript
Complexity
The time complexity is O(n), where n is the length of the string, because we iterate through the string to build groups and then analyse them. The space complexity is O(n) due to the groups array.
Approach 2: Segmentation and Swap Strategy
Break the string into segments where each segment consists of consecutive identical characters. Check if merging two segments by swapping can provide a longer substring of repeated characters. Consider character counts for more potential swaps.
This C function counts the segment length of consecutive similar characters. It checks if additional swaps can be utilized from the frequency count of each character, and evaluates the maximum length possible.
Complexity
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(1) given the fixed size of character frequency array.
Approach 3: Sliding Window Technique with Frequency Count
Utilize a sliding window approach to compute the maximum length of repeated substring by maintaining two pointers and a frequency array for efficient tracking and swapping analysis.
The C program sets up a sliding window covering segments with the use of frequency arrays to efficiently compute changes required with swaps and the corresponding maximum repeatable segment length.
Complexity
Time Complexity: O(n) using sliding window and frequency array.
Space Complexity: O(1) for fixed character count array.
Approach 4: Two Pointers
First, we use a hash table or array cnt to count the occurrence of each character in the string text.
Next, we define a pointer i, initially i = 0. Each time, we set the pointer j to i, and continuously move j to the right until the character pointed by j is different from the character pointed by i. At this time, we get a substring text[i..j-1] of length l = j - i, where all characters are the same.
Then we skip the character pointed by the pointer j, and continue to move the pointer k to the right until the character pointed by k is different from the character pointed by i. At this time, we get a substring text[j+1..k-1] of length r = k - j - 1, where all characters are the same. So the longest single-character repeated substring we can get by at most one swap operation is min(l + r + 1, cnt[text[i]]). Next, we move the pointer i to j and continue to find the next substring. We take the maximum length of all substrings that meet the conditions.
The time complexity is O(n), and the space complexity is O(C). Here, n is the length of the string, and C is the size of the character set. In this problem, C = 26.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Group Counting and Swap | The time complexity is |
| Segmentation and Swap Strategy | Time Complexity: O(n) where n is the length of the string. |
| Sliding Window Technique with Frequency Count | Time Complexity: O(n) using sliding window and frequency array. |
| Two Pointers | — |
Detailed Complexity Analysis
| 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 |
Video Solution
LeetCode 1156 | Swap For Longest Repeated Character Substring • leetuition • 8,140 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Swap For Longest Repeated Character Substring easy or hard?
Swap For Longest Repeated Character Substring Python/Java solution
How to solve Swap For Longest Repeated Character Substring in O(n)?
What is the best approach for Swap For Longest Repeated Character Substring?
Is Swap For Longest Repeated Character Substring asked at Google/Amazon/Meta?
What data structure is used in Swap For Longest Repeated Character Substring?
What is the time complexity of Swap For Longest Repeated Character Substring?
Ready to solve this problem?
Practice Swap For Longest Repeated Character Substring with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor