原文链接: https://leetcode-cn.com/problems/swap-for-longest-repeated-character-substring

英文原文

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", 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 <= 2 * 104
• text consist of lowercase English characters only.

中文题目

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。

给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。

 

示例 1：

输入：text = "ababa"
输出：3

示例 2：

输入：text = "aaabaaa"
输出：6

示例 3：

输入：text = "aaabbaaa"
输出：4

示例 4：

输入：text = "aaaaa"
输出：5

示例 5：

输入：text = "abcdef"
输出：1

 

提示：

• 1 <= text.length <= 20000
• text 仅由小写英文字母组成。

通过代码

高赞题解

1. 通过滑动窗口，记录索引i的左侧连续重复的字符的个数和右边连续字符的个数,并记录连续的字符的最长长度；
2. 索引i的左侧连续的重复个数为left[i-1],右侧连续重复的个数为right[i+1],主要分为以下三种情况:

   ```ans 
   ```text[i+1]```的字符总数大于```right[i+1]```, ```ans = max(ans,right[i+1]+1)```，这时从其他位置交换一个字符即可;
   ```text[i-1] == text[i+1]``` 且 ```text[i-1] != text[i]```，这时就需要进行链接前后的字符串，从其他地方找一相同的字符与```text[i]```进行交换，这时需要计算是否其他地方还有剩余的与```text[i]```相同的字符，通过比较```count[text[i-1]-'a']```与 ```left[i-1] + right[i+1]```是否相等, 即判断```count[text[i-1]-'a'] == (left[i-1] + right[i+1])```;
   

   class Solution {
   public:
   int maxRepOpt1(string text) {

    int ans = 1;
    int n = text.size();
    int c = 0;
    vector<int> left(n,1);
    vector<int> right(n,1);
    vector<int> count(26,0);
    
    for(int i = 0;i < n; ++i){
        count[text[i]-'a']++;
    }
    c = 1;
    for(int i = 1;i < n; ++i){
        if(text[i] == text[i-1]){
            c++;
        }else{
            c = 1;
        }
        left[i] = c;
        ans = max(ans,left[i]);
    }
    c = 1;
    for(int i = n-2; i >= 0; --i){
        if(text[i] == text[i+1]){
            c++;
        }else{
            c = 1;
        }
        right[i] = c;
        ans = max(ans,right[i]);
    }
    
    for(int i = 1;i < n-1; ++i){
        if(count[text[i-1]-'a'] > left[i-1]){
            ans = max(ans,left[i-1]+1);
        }
        if(count[text[i+1]-'a'] > right[i+1]){
            ans = max(ans,right[i+1]+1);
        }
        if(text[i-1] == text[i+1] && text[i-1] != text[i]){
            if(count[text[i-1]-'a'] > (left[i-1] + right[i+1])){
                ans = max(ans,left[i-1]+right[i+1]+1);
            }else{
                ans = max(ans,left[i-1]+right[i+1]);
            }
        }
    }
    
    return ans;
   

   }
   };
   ```

统计信息

通过次数	提交次数	AC比率
5232	12138	43.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言