Medium

题目描述

给你一个字符串 text，你可以交换其中任意两个字符。

返回具有相同字符的最长子字符串的长度。

示例 1：

输入：text = "ababa"
输出：3
解释：我们可以把第一个 'b' 和最后一个 'a' 交换，或者把最后一个 'b' 和第一个 'a' 交换。然后，最长的重复字符子串是长度为 3 的 "aaa"。

示例 2：

输入：text = "aaabaaa"
输出：6
解释：把 'b' 和最后一个 'a'（或第一个 'a'）交换，我们得到最长重复字符子串 "aaaaaa"，长度为 6。

示例 3：

输入：text = "aaaaa"
输出：5
解释：无需交换，最长重复字符子串是 "aaaaa"，长度为 5。

约束条件：

  • 1 <= text.length <= 2 * 10^4
  • text 只包含小写英文字母。

提示：

  • 有两种情况：一个字符块，或者两个字符块之间只有一个不同字符。通过保持字符串的行程编码版本，我们可以轻松检查这些情况。

解题思路

这道题要求通过交换任意两个字符来获得最长的重复字符子串。核心思路是：对于每个字符，找到能形成的最长连续段。

主要有两种可能的情况：

  1. 连续的字符块：直接统计连续相同字符的长度
  2. 被一个不同字符分隔的两个字符块：形如 aaa?aaa 的模式，其中 ? 是不同字符

解法分析：

  • 方法一：滑动窗口（推荐）：对每个字符使用滑动窗口，维护窗口内最多有一个不是目标字符的字符，记录最大窗口长度
  • 方法二：行程编码：按提示进行行程编码，然后检查相邻的同字符块

滑动窗口解法：

  1. 首先统计每个字符的总频次
  2. 对于每个字符，使用滑动窗口技术，窗口内允许最多有一个非目标字符
  3. 当窗口内非目标字符超过1个时，收缩左边界
  4. 记录每个字符能达到的最大窗口长度，但不能超过该字符的总数

时间复杂度为 O(26n) = O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int maxRepOpt1(string text) {
        vector<int> count(26, 0);
        for (char c : text) {
            count[c - 'a']++;
        }
        
        int maxLen = 0;
        
        for (int target = 0; target < 26; target++) {
            if (count[target] == 0) continue;
            
            int left = 0, right = 0;
            int targetCount = 0, otherCount = 0;
            
            while (right < text.length()) {
                if (text[right] - 'a' == target) {
                    targetCount++;
                } else {
                    otherCount++;
                }
                
                while (otherCount > 1) {
                    if (text[left] - 'a' == target) {
                        targetCount--;
                    } else {
                        otherCount--;
                    }
                    left++;
                }
                
                maxLen = max(maxLen, min(targetCount + otherCount, count[target]));
                right++;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def maxRepOpt1(self, text: str) -> int:
        from collections import Counter
        
        count = Counter(text)
        max_len = 0
        
        for target in count:
            left = 0
            target_count = 0
            other_count = 0
            
            for right in range(len(text)):
                if text[right] == target:
                    target_count += 1
                else:
                    other_count += 1
                
                while other_count > 1:
                    if text[left] == target:
                        target_count -= 1
                    else:
                        other_count -= 1
                    left += 1
                
                max_len = max(max_len, min(target_count + other_count, count[target]))
        
        return max_len

public class Solution {
    public int MaxRepOpt1(string text) {
        int[] count = new int[26];
        foreach (char c in text) {
            count[c - 'a']++;
        }
        
        int maxLen = 0;
        
        for (int target = 0; target < 26; target++) {
            if (count[target] == 0) continue;
            
            int left = 0;
            int targetCount = 0, otherCount = 0;
            
            for (int right = 0; right < text.Length; right++) {
                if (text[right] - 'a' == target) {
                    targetCount++;
                } else {
                    otherCount++;
                }
                
                while (otherCount > 1) {
                    if (text[left] - 'a' == target) {
                        targetCount--;
                    } else {
                        otherCount--;
                    }
                    left++;
                }
                
                maxLen = Math.Max(maxLen, Math.Min(targetCount + otherCount, count[target]));
            }
        }
        
        return maxLen;
    }
}

var maxRepOpt1 = function(text) {
    const count = new Array(26).fill(0);
    for (const c of text) {
        count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    let maxLen = 0;
    
    for (let target = 0; target < 26; target++) {
        if (count[target]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(26n) = O(n)
空间复杂度O(26) = O(1)

其中 n 是字符串的长度。我们对每个可能的字符（最多26个小写字母）都执行一次滑动窗口遍历，每次遍历需要O(n)时间。空间复杂度为常数，只需要存储字符频次数组。