单字符重复子串的最大长度【L1156】
如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。
给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。
思路：贪心+滑动窗口
为了获得最达长度的单字符重复子串，我们一定是找到以某个字符text[i]为首的最长子串[i,j−1]；然后跳过一个不同的字符text[j]，继续向后搜索最长重复子串[j+1,k−1]，为了使长度增大，我们应该从其他位置替换一个相同字符至位置j，那么此时最长重复子串为text[i，k−1]，但是还需要判断字符text[i]的数量与字符串长度的关系k−1−i+1
如果该字符的数量count大于等于k−i，那么说明可以从其他位置替换一个相同字符，此时最长重复子串长度为该字符的数量k−i
如果该字符的数量小于k−1−i+1，那么说明所有字符都在前后子串中，只能将首或者尾字符进行交换，此时最长重复子串长度为该字符的数量count
下一个字符从字符text[j]开始搜索，忽略t e x t [ i , j − 1 ] 内的字符一定不是最优解，因为其前缀重复子串不是最优的
- 实现
class Solution { public int maxRepOpt1(String text) { int n = text.length(); int[] count = new int[26]; int res = 0; for (int i = 0; i < n; i++){ count[text.charAt(i) - 'a']++; } int i = 0; while (i < n){ // 搜索最长重复子串text[i, j - 1] int j = i + 1; while (j < n && text.charAt(i) == text.charAt(j)){ j++; } // 搜索最长重复子串text[j + 1, k - 1] int k = j + 1; while (k < n && text.charAt(i) == text.charAt(k)){ k++; } res = Math.max(res, Math.min(k - i, count[text.charAt(i) - 'a'])); i = j; } return res; } }
复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( C )
![[LeetCode] 无重复字符的最长子串 & 最长回文子串](https://ucc.alicdn.com/3q7gnmkge2hyc_20230530_777afd9868c94a0dade08ab2c349217a.png?x-oss-process=image/resize,h_160,m_lfit)
