# 1156. Swap For Longest Repeated Character Substring

Given a string `text`, we are allowed to swap two of the characters in the string. Find 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", which its length is 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", which its length is 6.
``````

Example 3:

``````Input: text = "aaabbaaa"
Output: 4
``````

Example 4:

``````Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.
``````

Example 5:

``````Input: text = "abcdef"
Output: 1
``````

Constraints:

• `1 <= text.length <= 20000`
• `text` consist of lowercase English characters only.

``````class Solution {
public:
int maxRepOpt1(string text) {
int res = 0, n = text.size();
unordered_map<char, int> charCnt;
for (char c : text) ++charCnt[c];
for (int i = 0; i < n; ++i) {
char cur = text[i];
int j = i, cnt = 0, diff = 0;
while (j < n && (text[j] == cur || diff == 0) && cnt < charCnt[cur]) {
if (cur != text[j]) {
++diff;
i = j - 1;
}
++cnt;
++j;
}
res = max(res, cnt);
}
for (int i = n - 1; i >= 0; --i) {
char cur = text[i];
int j = i, cnt = 0, diff = 0;
while (j >= 0 && (text[j] == cur || diff == 0) && cnt < charCnt[cur]) {
if (cur != text[j]) {
++diff;
i = j + 1;
}
++cnt;
--j;
}
res = max(res, cnt);
}
return res;
}
};
``````

``````class Solution {
public:
int maxRepOpt1(string text) {
int res = 0, n = text.size();
unordered_map<char, vector<int>> idxMap;
for (int i = 0; i < n; ++i) idxMap[text[i]].push_back(i);
for (char c = 'a'; c <= 'z'; ++c) {
int cnt = 1, cnt2 = 0, mx = 0;
for (int i = 1; i < idxMap[c].size(); ++i) {
if (idxMap[c][i] == idxMap[c][i - 1] + 1) {
++cnt;
} else {
cnt2 = (idxMap[c][i] == idxMap[c][i - 1] + 2) ? cnt : 0;
cnt = 1;
}
mx = max(mx, cnt + cnt2);
}
res = max(res, mx + (idxMap[c].size() > mx ? 1 : 0));
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1156

https://leetcode.com/problems/swap-for-longest-repeated-character-substring/

https://leetcode.com/problems/swap-for-longest-repeated-character-substring/discuss/355922/C%2B%2B-2-approaches

https://leetcode.com/problems/swap-for-longest-repeated-character-substring/discuss/355866/Intuitive-Java-Solution-With-Explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation