Swap For Longest Repeated Character Substring — Solution
Swap For Longest Repeated Character Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Swap For Longest Repeated Character Substring is a medium coding problem on strings, hash table and binary search, asked in Amazon, Google, Intuit and Nutanix interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Binary Search, Sliding Window
- Asked at: Amazon, Google, Intuit, Nutanix
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You may swap two characters of text at most once (any two positions, not necessarily adjacent).
Return the length of the longest substring of a single repeated character you can obtain.
Example 1
Input: text = "ababa"
Output: 3
Explanation: Swapping the first b with the last a gives "aaaba".
Example 2
Input: text = "aaabaaa"
Output: 6
Explanation: Swapping the b with an a outside joins the two runs.
Example 3
Input: text = "aaaaa"
Output: 5
Explanation: Nothing to gain — the swap can be a no-op.
Constraints
1 <= text.length <= 20000text consists of lowercase English letters.
Hints for Swap For Longest Repeated Character Substring
Hint 1
Break the string into maximal runs of equal characters.
Hint 2
One swap can extend a single run by one — but only if that character occurs somewhere outside it.
Hint 3
Two runs of the same character separated by exactly one other character can be joined, again capped by the total occurrences.
How to solve Swap For Longest Repeated Character Substring
The answer always comes from one of two shapes: a single run extended by one borrowed character, or two same-character runs bridged across a single gap. Both are capped by how many of that character exist in total, since a swap moves a character rather than creating one.
Approach
- Tally the total occurrences of each character.
- Split the text into runs
(char, length). - For each run, consider
min(length + 1, total[char]). - When the next run is a single character and the one after repeats the same letter, also consider
min(len1 + len2 + 1, total[char]).
Why it works
A swap brings in at most one extra copy of the target character, so no answer can exceed total[char], and the + 1 is only realisable when a spare copy exists outside the run — which the min enforces. Any optimal final run occupies contiguous positions, so it either sits inside one original run plus one borrowed slot, or spans exactly one foreign character between two runs; a gap of two or more cannot be closed by a single swap.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Forgetting the
minwith the total count over-counts when every copy of the character is already inside the run. - Bridging across a gap wider than one character is not achievable with one swap.
- The bridge case must check the run after the gap has the same character.
Reference solution
Python
def maxRepOpt1(text: str) -> int:
total = {}
for ch in text:
total[ch] = total.get(ch, 0) + 1
runs = []
i = 0
n = len(text)
while i < n:
j = i
while j < n and text[j] == text[i]:
j += 1
runs.append((text[i], j - i))
i = j
best = 0
for r in range(len(runs)):
c, length = runs[r]
best = max(best, min(length + 1, total[c]))
if r + 2 < len(runs) and runs[r + 1][1] == 1 and runs[r + 2][0] == c:
best = max(best, min(length + runs[r + 2][1] + 1, total[c]))
return bestJava
public static int maxRepOpt1(String text) {
int n = text.length();
int[] total = new int[26];
for (int i = 0; i < n; i++) total[text.charAt(i) - 'a']++;
List<int[]> runs = new ArrayList<>();
int p = 0;
while (p < n) {
int q = p;
while (q < n && text.charAt(q) == text.charAt(p)) q++;
runs.add(new int[] { text.charAt(p) - 'a', q - p });
p = q;
}
int best = 0;
for (int r = 0; r < runs.size(); r++) {
int c = runs.get(r)[0], len = runs.get(r)[1];
best = Math.max(best, Math.min(len + 1, total[c]));
if (r + 2 < runs.size() && runs.get(r + 1)[1] == 1 && runs.get(r + 2)[0] == c) {
best = Math.max(best, Math.min(len + runs.get(r + 2)[1] + 1, total[c]));
}
}
return best;
}C++
int maxRepOpt1(string text) {
int n = (int) text.size();
vector<int> total(26, 0);
for (int i = 0; i < n; i++) total[text[i] - 'a']++;
vector<pair<int, int>> runs;
int p = 0;
while (p < n) {
int q = p;
while (q < n && text[q] == text[p]) q++;
runs.push_back(make_pair(text[p] - 'a', q - p));
p = q;
}
int best = 0;
for (int r = 0; r < (int) runs.size(); r++) {
int c = runs[r].first, len = runs[r].second;
best = max(best, min(len + 1, total[c]));
if (r + 2 < (int) runs.size() && runs[r + 1].second == 1 && runs[r + 2].first == c) {
best = max(best, min(len + runs[r + 2].second + 1, total[c]));
}
}
return best;
}JavaScript
var maxRepOpt1 = function(text) {
var n = text.length;
var total = {};
for (var i = 0; i < n; i++) {
var ch = text.charAt(i);
total[ch] = (total[ch] || 0) + 1;
}
var runs = [];
var p = 0;
while (p < n) {
var q = p;
while (q < n && text.charAt(q) === text.charAt(p)) q++;
runs.push([text.charAt(p), q - p]);
p = q;
}
var best = 0;
for (var r = 0; r < runs.length; r++) {
var c = runs[r][0], len = runs[r][1];
best = Math.max(best, Math.min(len + 1, total[c]));
if (r + 2 < runs.length && runs[r + 1][1] === 1 && runs[r + 2][0] === c) {
best = Math.max(best, Math.min(len + runs[r + 2][1] + 1, total[c]));
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets