class Solution:
def maxRepOpt1(self, text: str) -> int:
from collections import Counter, defaultdict
n = len(text)
count = Counter(text)
groups = []
i = 0
while i < n:
j = i
while j < n and text[j] == text[i]:
j += 1
groups.append((text[i], i, j - 1)) # (char, start, end)
i = j
ans = 0
for idx, (char, start, end) in enumerate(groups):
length = end - start + 1
# Option 1: extend by swapping in another char if available
if count[char] > length:
ans = max(ans, length + 1)
else:
ans = max(ans, length)
# Option 2: merge separated groups
if idx + 2 < len(groups):
next_char, next_start, next_end = groups[idx + 2]
if groups[idx + 1][1] == end + 1 and groups[idx + 1][2] == next_start - 1 and \
groups[idx + 1][0] != char and next_char == char and next_start == end + 2:
merged_len = (end - start + 1) + (next_end - next_start + 1)
if count[char] > merged_len:
ans = max(ans, merged_len + 1)
else:
ans = max(ans, merged_len)
return ans
class Solution {
public:
int maxRepOpt1(string text) {
unordered_map<char, int> count;
int n = text.size();
for (char c : text) count[c]++;
vector<tuple<char, int, int>> groups;
int i = 0;
while (i < n) {
int j = i;
while (j < n && text[j] == text[i]) j++;
groups.push_back({text[i], i, j - 1});
i = j;
}
int ans = 0;
for (int idx = 0; idx < groups.size(); ++idx) {
char ch;
int start, end;
tie(ch, start, end) = groups[idx];
int len = end - start + 1;
if (count[ch] > len) ans = max(ans, len + 1);
else ans = max(ans, len);
if (idx + 2 < groups.size()) {
char ch2, ch3;
int s2, e2, s3, e3;
tie(ch2, s2, e2) = groups[idx + 1];
tie(ch3, s3, e3) = groups[idx + 2];
if (s2 == end + 1 && e2 == s3 - 1 && ch2 != ch && ch3 == ch && s3 == end + 2) {
int merged_len = (end - start + 1) + (e3 - s3 + 1);
if (count[ch] > merged_len) ans = max(ans, merged_len + 1);
else ans = max(ans, merged_len);
}
}
}
return ans;
}
};
class Solution {
public int maxRepOpt1(String text) {
int n = text.length();
Map<Character, Integer> count = new HashMap<>();
for (char c : text.toCharArray()) count.put(c, count.getOrDefault(c, 0) + 1);
List<int[]> groups = new ArrayList<>();
int i = 0;
while (i < n) {
int j = i;
while (j < n && text.charAt(j) == text.charAt(i)) j++;
groups.add(new int[]{text.charAt(i), i, j - 1});
i = j;
}
int ans = 0;
for (int idx = 0; idx < groups.size(); ++idx) {
int[] group = groups.get(idx);
char ch = (char)group[0];
int start = group[1], end = group[2];
int len = end - start + 1;
if (count.get(ch) > len) ans = Math.max(ans, len + 1);
else ans = Math.max(ans, len);
if (idx + 2 < groups.size()) {
int[] group2 = groups.get(idx + 1), group3 = groups.get(idx + 2);
char ch2 = (char)group2[0], ch3 = (char)group3[0];
int s2 = group2[1], e2 = group2[2], s3 = group3[1], e3 = group3[2];
if (s2 == end + 1 && e2 == s3 - 1 && ch2 != ch && ch3 == ch && s3 == end + 2) {
int merged_len = (end - start + 1) + (e3 - s3 + 1);
if (count.get(ch) > merged_len) ans = Math.max(ans, merged_len + 1);
else ans = Math.max(ans, merged_len);
}
}
}
return ans;
}
}
var maxRepOpt1 = function(text) {
const n = text.length;
const count = {};
for (let c of text) count[c] = (count[c] || 0) + 1;
const groups = [];
let i = 0;
while (i < n) {
let j = i;
while (j < n && text[j] === text[i]) j++;
groups.push([text[i], i, j - 1]);
i = j;
}
let ans = 0;
for (let idx = 0; idx < groups.length; ++idx) {
const [ch, start, end] = groups[idx];
const len = end - start + 1;
if (count[ch] > len) ans = Math.max(ans, len + 1);
else ans = Math.max(ans, len);
if (idx + 2 < groups.length) {
const [ch2, s2, e2] = groups[idx + 1];
const [ch3, s3, e3] = groups[idx + 2];
if (s2 === end + 1 && e2 === s3 - 1 && ch2 !== ch && ch3 === ch && s3 === end + 2) {
const merged_len = (end - start + 1) + (e3 - s3 + 1);
if (count[ch] > merged_len) ans = Math.max(ans, merged_len + 1);
else ans = Math.max(ans, merged_len);
}
}
}
return ans;
};
Given a string text, you can swap any two characters (even if they are the same) at most once. After swapping, find the length of the longest substring that consists of only one repeated character. You must return this maximum possible length.
text at most once (or not at all).
Example:
Input: text = "ababa"
Output: 3
Explanation: Swap the first and last 'a' to get "aabaa", where the longest substring of repeated 'a' is length 3.
At first glance, it may seem like we need to try every possible swap and check the result, but this would be very inefficient for large strings. Instead, we want to think about the problem in terms of "blocks" or "groups" of the same character. The core idea is that swapping can help us either:
By focusing on these cases, we can avoid brute-forcing every possible swap and instead analyze the structure of the string. We also need to count how many times each character occurs in the string, since we can't create more than exist.
Let's break down the optimized solution step-by-step:
text, count how many times it appears. This helps us know if we can extend a group by swapping in another occurrence.
text and record each contiguous group of the same character, noting its start and end indices.
aaaXaaa), and there is at least one more occurrence of that character elsewhere, we can swap to merge them into a longer group.
This approach efficiently finds the optimal answer by analyzing the block structure and available swaps, using hash maps for fast lookups.
Let's walk through the sample input text = "ababa":
a appears 3 times, b appears 2 times.
3.
Brute-force approach: Trying every possible swap would take O(N2) time, where N is the length of text, since there are O(N2) pairs of indices and each check could take O(N).
Optimized approach: The above solution:
Space complexity: O(N) for storing groups and character counts.
The key to solving the "Swap For Longest Repeated Character Substring" problem efficiently is to recognize patterns in the string—specifically, groups of repeated characters and the potential to merge or extend these groups with a single swap. By counting character occurrences and analyzing group positions, we can determine the optimal swap (if any) and find the answer in linear time. This approach is both elegant and practical, avoiding unnecessary brute-force checks.