难度: Medium
如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。
给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。
示例 1：
输入：text = "ababa" 输出：3
示例 2：
输入：text = "aaabaaa" 输出：6
示例 3：
输入：text = "aaabbaaa" 输出：4
示例 4：
输入：text = "aaaaa" 输出：5
示例 5：
输入：text = "abcdef" 输出：1
提示：
1 <= text.length <= 20000text 仅由小写英文字母组成。运行时间: 43 ms
内存: 17.3 MB
class Solution:
def maxRepOpt1(self, text: str) -> int:
appear_times = [0 for _ in range(26)]
max_consec = [0 for _ in range(26)]
max_gap = [0 for _ in range(26)]
dp = [(1,1) for _ in range(len(text))]
dp[0] = (1,1)
appear_times[ord(text[0]) - ord('a')] += 1
max_consec[ord(text[0]) - ord('a')] = 1
for i in range(1, len(text)):
index = ord(text[i]) - ord('a')
if text[i] == text[i - 1]:
dp[i] = (dp[i-1][0] + 1, dp[i - 1][1] + 1)
if dp[i][0] > max_consec[index]:
max_consec[index] = dp[i][0]
if dp[i][1] > max_gap[index]:
max_gap[index] = dp[i][1]
else:
appear_times[index] += 1
if i >= 2 and text[i] == text[i - 2]:
dp[i] = (1, dp[i - 2][0] + 1)
else:
dp[i] = (1, 1)
if dp[i][0] > max_consec[index]:
max_consec[index] = dp[i][0]
if dp[i][1] > max_gap[index]:
max_gap[index] = dp[i][1]
ans = 0
for i in range(26):
if appear_times[i] > 2:
ans = max(max_gap[i] + 1, ans)
elif appear_times[i] == 2:
ans = max(ans, max_consec[i] + 1, max_gap[i])
elif appear_times[i] == 1:
ans = max(ans, max_consec[i])
return ans
题解的主要思路是通过动态规划和额外的统计数组来解决问题。首先，使用一个数组 `appear_times` 来记录每个字符在文本中出现的次数。同时，使用两个数组 `max_consec` 和 `max_gap` 分别记录每个字符连续出现的最大长度和可能通过一次交换后能达到的最大长度。动态规划数组 `dp` 的每个元素包含两个值，分别表示当前位置连续的字符长度和可能的最长交换后长度。在遍历字符串时，根据当前字符是否与前一个字符相同来更新 `dp` 数组，以及对应的 `max_consec` 和 `max_gap`。最后，根据字符的出现次数，利用 `max_consec` 和 `max_gap` 计算可能的最大长度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maxRepOpt1(self, text: str) -> int:
# 初始化字符计数器和动态规划数组
appear_times = [0 for _ in range(26)]
max_consec = [0 for _ in range(26)]
max_gap = [0 for _ in range(26)]
dp = [(1,1) for _ in range(len(text))]
dp[0] = (1,1)
appear_times[ord(text[0]) - ord('a')] += 1
max_consec[ord(text[0]) - ord('a')] = 1
for i in range(1, len(text)):
index = ord(text[i]) - ord('a')
if text[i] == text[i - 1]:
# 更新连续相同字符的统计
dp[i] = (dp[i-1][0] + 1, dp[i - 1][1] + 1)
if dp[i][0] > max_consec[index]:
max_consec[index] = dp[i][0]
if dp[i][1] > max_gap[index]:
max_gap[index] = dp[i][1]
else:
appear_times[index] += 1
if i >= 2 and text[i] == text[i - 2]:
# 考虑通过一次交换修正为更长的子串
dp[i] = (1, dp[i - 2][0] + 1)
else:
dp[i] = (1, 1)
if dp[i][0] > max_consec[index]:
max_consec[index] = dp[i][0]
if dp[i][1] > max_gap[index]:
max_gap[index] = dp[i][1]
ans = 0
for i in range(26):
if appear_times[i] > 2:
# 可以通过交换获得更长的子串
ans = max(max_gap[i] + 1, ans)
elif appear_times[i] == 2:
ans = max(ans, max_consec[i] + 1, max_gap[i])
elif appear_times[i] == 1:
ans = max(ans, max_consec[i])
return ans
在代码中，`dp`数组的每个元素为一个元组，其中第一个值记录当前位置连续的相同字符的最大长度，而第二个值记录可能通过一次交换后能够达到的最大长度。当字符不连续时，此时`dp[i][1]`的计算需要判断当前字符与前前一个字符是否相同（即`text[i] == text[i - 2]`）。如果相同，表示通过交换`text[i - 1]`和`text[i]`之间的字符，可以将`text[i]`连到`text[i - 2]`之前形成的连续子串上，因此`dp[i][1] = dp[i - 2][0] + 1`。这种情况下，我们假设通过一次交换可以修正一个间断，从而增加连续子串的长度。如果不相同，则`dp[i][1]`重置为1，因为当前字符未能通过交换与前面的字符形成更长的连续子串。
代码中通过动态规划在`dp[i][1]`中记录可能通过一次交换后能达到的最大长度。这一计算基于当前字符是否能与它前面非连续的字符形成连续串。如果当前字符与前前字符相同，并且中间只有一个不同的字符，那么可以通过交换这个不同字符，将当前字符加入到前面的连续字符串中。因此，`dp[i][1]`在这种情况下会设置为`dp[i - 2][0] + 1`。此外，代码在更新`max_gap`数组时，会检查每个字符的`dp[i][1]`值，以确定通过一次交换可能达到的最大长度。
`max_gap`数组用于记录每个字符通过一次交换后可能达到的最大连续长度。在每次更新`dp[i][1]`时，它记录了当前字符通过一次交换后可能形成的最大连续区间。因此，每当`dp[i][1]`被计算时，代码会检查并更新`max_gap`数组中对应字符的最大值。这样，`max_gap`可以为每个字符存储通过一次优化交换后可能获得的最长连续子串长度。
确实如此，对于在字符串中只出现一次的字符，它的最大连续长度当然是1（因为它本身就是一个单独的字符），而`max_gap[i]`在此情况下也不会超过1，因为没有其他相同的字符进行交换。因此，对于只出现一次的字符，考虑交换来增加长度是没有意义的，所以最大长度直接是`max_consec[i]`，即1。这里的处理逻辑正确地反映了对于单个字符交换的不可行性。