Swap For Longest Repeated Character Substring solution and explanation
Google
8 more videos on this problem
LeetCode 1156 | Swap For Longest Repeated Character Substringleetuition · 10:36 · 8K views
1156 Swap For Longest Repeated Character Substring (Weekly Contest 149)Kelvin Chandra · 7:34 · 4K views
1156. Swap For Longest Repeated Character Substring (Leetcode Medium)Programming Live with Larry · 16:34 · 1K views
LeetCode 1156. Swap For Longest Repeated Character SubstringcoderZ · 12:13 · 1K views
1156. Swap For Longest Repeated Character SubstringMuerde un zombie · 9:29 · 396 views
Swap For Longest Repeated Character Substring | Optimal Solution EXPLAINED C++ | LeetCode 1156DLG_Coding · 14:35 · 340 views
How to Solve in a Tech Interview | Swap For Longest Repeated Character Substring | LeetCode 1156DLG_Coding · 1:28:01 · 79 views
LeetCode 1156: Swap For Longest Repeated Character SubstringAlitaCode · 28:48 · 51 views
No Sound Leetcode 1156: Swap for Longest Repeated Character SubstringExtremeProgrammer · 3:24 · 27 views
The problem
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.
def maxRepOpt1(text: str) -> int:
from collections import Counter, defaultdict
count = Counter(text)
groups = [] # stores (character, length)
prev_char = text[0]
length = 1
for i in range(1, len(text)):
if text[i] == prev_char:
length += 1
else:
groups.append((prev_char, length))
prev_char = text[i]
length = 1
groups.append((prev_char, length))
max_len = 0
for i in range(len(groups)):
char, length = groups[i]
max_len = max(max_len, length if count[char] <= length else length + 1)
if i > 0 and i < len(groups) - 1 and groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1:
max_len = max(max_len, groups[i - 1][1] + groups[i + 1][1] + (1 if count[groups[i - 1][0]] > groups[i - 1][1] + groups[i + 1][1] else 0))
return max_lenfunction maxRepOpt1(text) {
const count = {};
const groups = [];
let prevChar = text[0];
let length = 1;
for (let i = 1; i < text.length; i++) {
if (text[i] !== prevChar) {
groups.push([prevChar, length]);
prevChar = text[i];
length = 1;
} else {
length++;
}
}
groups.push([prevChar, length]);
for (const char of text) {
count[char] = (count[char] || 0) + 1;
}
let maxLen = 0;
for (let i = 0; i < groups.length; i++) {
const [char, length] = groups[i];
maxLen = Math.max(maxLen, length < count[char] ? length + 1 : length);
if (i > 0 && i < groups.length - 1 && groups[i - 1][0] === groups[i + 1][0] && groups[i][1] === 1) {
maxLen = Math.max(maxLen, groups[i - 1][1] + groups[i + 1][1] + (count[groups[i - 1][0]] > groups[i - 1][1] + groups[i + 1][1] ? 1 : 0));
}
}
return maxLen;
}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.
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.
def maxRepOpt1(text: str) -> int:
n = len(text)
count = {c: text.count(c) for c in set(text)}
max_len = 0
i = 0
while i < n:
c = text[i]
start = i
while i < n and text[i] == c:
i += 1
len1 = i - start
max_len = max(max_len, len1 + (len1 < count[c]))
j = i + 1
while j < n and text[j] == c:
j += 1
len2 = j - i
if j < n and text[j] == c:
if len1 + len2 < count[c]:
max_len = max(max_len, len1 + len2 + 1)
i = start + len1
return max_len
print(maxRepOpt1("ababa"))import java.util.HashMap;
public class Solution {
public int maxRepOpt1(String text) {
int n = text.length();
HashMap<Character, Integer> count = new HashMap<>();
for (char c : text.toCharArray()) {
count.put(c, count.getOrDefault(c, 0) + 1);
}
int maxLen = 0;
for (int i = 0; i < n;) {
char c = text.charAt(i);
int start = i;
while (i < n && text.charAt(i) == c) i++;
int len1 = i - start;
int j = i + 1;
while (j < n && text.charAt(j) == c) j++;
maxLen = Math.max(maxLen, len1 + (len1 < count.get(c) ? 1 : 0));
if (j < n) {
int len2 = j - i;
if (text.charAt(j) == c && len1 + len2 < count.get(c))
maxLen = Math.max(maxLen, len1 + len2 + 1);
}
i = start + len1;
}
return maxLen;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.maxRepOpt1("ababa"));
}
}#include <iostream>
#include <unordered_map>
using namespace std;
int maxRepOpt1(string text) {
unordered_map<char, int> count;
int maxLen = 0, n = text.size();
for (char c : text) count[c]++;
for (int i = 0; i < n;) {
char c = text[i];
int start = i;
while (i < n && text[i] == c) i++;
int len1 = i - start;
int j = i + 1;
while (j < n && text[j] == c) j++;
maxLen = max(maxLen, len1 + (len1 < count[c])) ;
int len2 = j - i;
if (j < n) {
if (text[j] == c && len1 + len2 < count[c])
maxLen = max(maxLen, len1 + len2 + 1);
}
i = start + len1;
}
return maxLen;
}
int main() {
cout << maxRepOpt1("ababa") << endl;
return 0;
}function maxRepOpt1(text) {
const n = text.length;
const count = {};
for (const char of text) {
count[char] = (count[char] || 0) + 1;
}
let maxLen = 0;
for (let i = 0; i < n;) {
const c = text[i];
let start = i;
while (i < n && text[i] === c) i++;
let len1 = i - start;
maxLen = Math.max(maxLen, len1 + (len1 < count[c] ? 1 : 0));
let j = i + 1;
while (j < n && text[j] === c) j++;
let len2 = j - i;
if (j < n && text[j] === c) {
if (len1 + len2 < count[c])
maxLen = Math.max(maxLen, len1 + len2 + 1);
}
i = start + len1;
}
return maxLen;
}
console.log(maxRepOpt1("ababa"));#include <stdio.h>
#include <string.h>
int maxRepOpt1(char* text) {
int n = strlen(text);
int count[26] = {0};
int maxLen = 0;
for (int i = 0; i < n; ++i) {
count[text[i] - 'a']++;
}
for (int i = 0; i < n;) {
char c = text[i];
int start = i;
while (i < n && text[i] == c) i++;
int len1 = i - start;
int j = i + 1;
while (j < n && text[j] == c) j++;
maxLen = (len1 > maxLen) ? len1 : maxLen;
if (len1 + 1 <= count[c - 'a'])
maxLen = (len1 + 1 > maxLen) ? len1 + 1 : maxLen;
if (j < n) {
int len2 = j - i;
if (text[j] == c && len1 + len2 <= count[c - 'a'])
maxLen = (len1 + len2 + 1 > maxLen) ? len1 + len2 + 1 : maxLen;
}
i = start + len1;
}
return maxLen;
}
int main() {
char text[] = "ababa";
printf("Longest length = %d\n", maxRepOpt1(text));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxRepOpt1(string text) {
int n = text.Length;
Dictionary<char, int> count = new Dictionary<char, int>();
foreach (char c in text) {
if (!count.ContainsKey(c)) count[c] = 0;
count[c]++;
}
int maxLen = 0;
for (int i = 0; i < n;) {
char c = text[i];
int start = i;
while (i < n && text[i] == c) i++;
int len1 = i - start;
maxLen = Math.Max(maxLen, len1 + (len1 < count[c] ? 1 : 0));
int j = i + 1;
while (j < n && text[j] == c) j++;
if (j < n && text[j] == c) {
int len2 = j - i;
if (len1 + len2 < count[c])
maxLen = Math.Max(maxLen, len1 + len2 + 1);
}
i = start + len1;
}
return maxLen;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MaxRepOpt1("ababa"));
}
}In Python, this script uses dictionaries for efficiently counting characters and manages segments to determine swap-based maximum repeatable lengths.
Time Complexity: O(n)
Space Complexity: O(1)
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.
def maxRepOpt1(text: str) -> int:
count = [0] * 26
n = len(text)
for c in text:
count[ord(c) - ord('a')] += 1
start = 0
max_len = 0
current_max = 0
for end in range(n):
current_max += 1
candidate_max = current_max + (count[ord(text[end]) - ord('a')] > current_max)
max_len = max(max_len, candidate_max)
while count[ord(text[end]) - ord('a')] < current_max:
current_max -= 1
start += 1
return max_len
print(maxRepOpt1("ababa"))import java.util.Arrays;
public class Solution {
public int maxRepOpt1(String text) {
int[] count = new int[26];
int n = text.length();
for (char c : text.toCharArray())
count[c - 'a']++;
int start = 0, maxLen = 0, currentMax = 0;
for (int end = 0; end < n; end++) {
currentMax++;
int candidateMax = currentMax + (count[text.charAt(end) - 'a'] > currentMax ? 1 : 0);
maxLen = Math.max(maxLen, candidateMax);
while (count[text.charAt(end) - 'a'] < currentMax) {
currentMax--;
start++;
}
}
return maxLen;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.maxRepOpt1("ababa"));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxRepOpt1(string text) {
vector<int> count(26, 0);
int n = text.size();
for (char & c : text)
count[c - 'a']++;
int start = 0, max_len = 0, current_max = 0;
for (int end = 0; end < n; ++end) {
current_max++;
int candidate_max = current_max + (count[text[end] - 'a'] > current_max ? 1 : 0);
max_len = max(max_len, candidate_max);
while (count[text[end] - 'a'] < current_max) {
current_max--;
start++;
}
}
return max_len;
}
int main() {
cout << maxRepOpt1("ababa") << endl;
return 0;
}function maxRepOpt1(text) {
const count = new Array(26).fill(0);
const n = text.length;
for (let c of text) {
count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
let start = 0, maxLen = 0, currentMax = 0;
for (let end = 0; end < n; end++) {
currentMax++;
const charIndex = text[end].charCodeAt(0) - 'a'.charCodeAt(0);
const candidateMax = currentMax + (count[charIndex] > currentMax ? 1 : 0);
maxLen = Math.max(maxLen, candidateMax);
while (count[charIndex] < currentMax) {
currentMax--;
start++;
}
}
return maxLen;
}
console.log(maxRepOpt1("ababa"));#include <stdio.h>
#include <string.h>
int maxRepOpt1(char* text) {
int count[26] = {0};
int n = strlen(text);
for (int i = 0; i < n; i++)
count[text[i] - 'a']++;
int start = 0, max_len = 0, current_max = 0;
for (int end = 0; end < n; end++) {
current_max++;
int candidate_max = current_max + (count[text[end] - 'a'] > current_max ? 1 : 0);
max_len = max_len > candidate_max ? max_len : candidate_max;
while (count[text[end] - 'a'] < current_max) {
current_max--;
start++;
}
}
return max_len;
}
int main() {
char text[] = "ababa";
printf("Longest length = %d\n", maxRepOpt1(text));
return 0;
}using System;
public class Solution {
public int MaxRepOpt1(string text) {
int[] count = new int[26];
int n = text.Length;
foreach (char c in text)
count[c - 'a']++;
int start = 0, maxLen = 0, currentMax = 0;
for (int end = 0; end < n; end++) {
currentMax++;
int candidateMax = currentMax + (count[text[end] - 'a'] > currentMax ? 1 : 0);
maxLen = Math.Max(maxLen, candidateMax);
while (count[text[end] - 'a'] < currentMax) {
currentMax--;
start++;
}
}
return maxLen;
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MaxRepOpt1("ababa"));
}
}Using Python, this function applies sliding window logic in conjunction with a frequency count, offering an efficient way to dynamically compute potential maximum lengths of repeatable segments.
Time Complexity: O(n)
Space Complexity: O(1)
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.
function maxRepOpt1(text: string): number {
const idx = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
const cnt: number[] = new Array(26).fill(0);
for (const c of text) {
cnt[idx(c)]++;
}
let ans = 0;
let i = 0;
const n = text.length;
while (i < n) {
let j = i;
while (j < n && text[j] === text[i]) {
++j;
}
const l = j - i;
let k = j + 1;
while (k < n && text[k] === text[i]) {
++k;
}
const r = k - j - 1;
ans = Math.max(ans, Math.min(cnt[idx(text[i])], l + r + 1));
i = j;
}
return ans;
}func maxRepOpt1(text string) (ans int) {
cnt := [26]int{}
for _, c := range text {
cnt[c-'a']++
}
n := len(text)
for i, j := 0, 0; i < n; i = j {
j = i
for j < n && text[j] == text[i] {
j++
}
l := j - i
k := j + 1
for k < n && text[k] == text[i] {
k++
}
r := k - j - 1
ans = max(ans, min(l+r+1, cnt[text[i]-'a']))
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Group Counting and Swap | The time complexity is |
| Segmentation and Swap Strategy | Time Complexity: O(n) |
| Sliding Window Technique with Frequency Count | Time Complexity: O(n) |
| Two Pointers | – |
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 |
Frequently asked questions
Is Swap For Longest Repeated Character Substring easy or hard?
Swap For Longest Repeated Character Substring is classified as a Medium difficulty problem. The challenge comes from reasoning about how one swap can extend or merge character groups. Once you recognize the segmentation pattern or sliding window formulation, the implementation becomes straightforward.
Swap For Longest Repeated Character Substring Python/Java solution
Python and Java implementations typically start with counting character frequencies using an array of size 26. Then they iterate through the string to track repeating segments or maintain a sliding window that allows at most one mismatched character. Both implementations achieve O(n) time and O(1) extra space.
How to solve Swap For Longest Repeated Character Substring in O(n)?
First count the total occurrences of each character. Then scan the string and track contiguous segments or use a sliding window. If two segments of the same character are separated by one different character, combine their lengths and add one more if another identical character exists elsewhere. This keeps the algorithm linear while evaluating all possible swap improvements.
What is the best approach for Swap For Longest Repeated Character Substring?
The segmentation and swap strategy is the most intuitive and commonly recommended approach. It groups consecutive identical characters and checks whether two segments can merge by swapping a character from elsewhere. This method runs in O(n) time and O(1) space while clearly modeling how a single swap affects repeating substrings.
Is Swap For Longest Repeated Character Substring asked at Google/Amazon/Meta?
Problems involving longest repeating substrings and sliding window techniques appear frequently in interviews at companies like Google, Amazon, and Meta. Variants test understanding of string segmentation, frequency counting, and window expansion logic. Mastering this problem strengthens pattern recognition for many substring optimization questions.
What data structure is used in Swap For Longest Repeated Character Substring?
The core data structures are a frequency array or hash table to count characters and optionally a list of segments representing contiguous character groups. Some implementations also use a sliding window with two pointers. These structures allow constant-time character frequency lookups during the scan.
What is the time complexity of Swap For Longest Repeated Character Substring?
The optimal solutions run in O(n) time where n is the length of the string. The algorithm performs a single pass to count character frequencies and another linear scan to analyze segments or sliding windows. Space complexity is O(1) because only fixed-size character frequency arrays are needed.