Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Sliding Window
"ababa"
"aaabaaa"
"aaaaa"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1156: Swap For Longest Repeated Character Substring
class Solution {
public int maxRepOpt1(String text) {
int[] cnt = new int[26];
int n = text.length();
for (int i = 0; i < n; ++i) {
++cnt[text.charAt(i) - 'a'];
}
int ans = 0, i = 0;
while (i < n) {
int j = i;
while (j < n && text.charAt(j) == text.charAt(i)) {
++j;
}
int l = j - i;
int k = j + 1;
while (k < n && text.charAt(k) == text.charAt(i)) {
++k;
}
int r = k - j - 1;
ans = Math.max(ans, Math.min(l + r + 1, cnt[text.charAt(i) - 'a']));
i = j;
}
return ans;
}
}
// Accepted solution for LeetCode #1156: Swap For Longest Repeated Character Substring
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
}
# Accepted solution for LeetCode #1156: Swap For Longest Repeated Character Substring
class Solution:
def maxRepOpt1(self, text: str) -> int:
cnt = Counter(text)
n = len(text)
ans = i = 0
while i < n:
j = i
while j < n and text[j] == text[i]:
j += 1
l = j - i
k = j + 1
while k < n and text[k] == text[i]:
k += 1
r = k - j - 1
ans = max(ans, min(l + r + 1, cnt[text[i]]))
i = j
return ans
// Accepted solution for LeetCode #1156: Swap For Longest Repeated Character Substring
struct Solution;
impl Solution {
fn max_rep_opt1(text: String) -> i32 {
let s: Vec<u8> = text.bytes().collect();
let n = s.len();
let mut group: Vec<(u8, usize)> = vec![];
let mut count: Vec<usize> = vec![0; 26];
for i in 0..n {
count[(s[i] - b'a') as usize] += 1;
}
let mut prev = 1;
for i in 1..n {
if s[i] == s[i - 1] {
prev += 1;
} else {
group.push((s[i - 1], prev));
prev = 1;
}
}
group.push((s[n - 1], prev));
let mut res = 0;
for g in &group {
res = res.max(count[(g.0 - b'a') as usize].min(g.1 + 1));
}
for i in 1..group.len() - 1 {
if group[i - 1].0 == group[i + 1].0 && group[i].1 == 1 {
let b = group[i - 1].0;
res = res.max(count[(b - b'a') as usize].min(group[i - 1].1 + group[i + 1].1 + 1));
}
}
res as i32
}
}
#[test]
fn test() {
let text = "ababa".to_string();
let res = 3;
assert_eq!(Solution::max_rep_opt1(text), res);
let text = "aaabaaa".to_string();
let res = 6;
assert_eq!(Solution::max_rep_opt1(text), res);
let text = "aaabbaaa".to_string();
let res = 4;
assert_eq!(Solution::max_rep_opt1(text), res);
let text = "aaaaa".to_string();
let res = 5;
assert_eq!(Solution::max_rep_opt1(text), res);
let text = "abcdef".to_string();
let res = 1;
assert_eq!(Solution::max_rep_opt1(text), res);
}
// Accepted solution for LeetCode #1156: Swap For Longest Repeated Character Substring
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;
}
Use this to step through a reusable interview workflow for this problem.
For each starting index, scan the next k elements to compute the window aggregate. There are n−k+1 starting positions, each requiring O(k) work, giving O(n × k) total. No extra space since we recompute from scratch each time.
The window expands and contracts as we scan left to right. Each element enters the window at most once and leaves at most once, giving 2n total operations = O(n). Space depends on what we track inside the window (a hash map of at most k distinct elements, or O(1) for a fixed-size window).
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.