本文涉及的基础知识点

C++算法：滑动窗口及双指针总结

LeetCode1156. 单字符重复子串的最大长度

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。
给你一个字符串 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 仅由小写英文字母组成。

LeetCode滑动窗口

分别枚举单字符是’a’、‘b’、‘c’、’d’、‘e’$\cdots$。
不失一般性，令重复字符是a。
性质一：如果nums[i…j]只有0个1个字符不是a，且子串之外至少有一个a，则nums[i…j]是重复子串。
$⟺$ 如果nums[i…j]只有0个1个字符不是a,不超过a的数量。
性质二：如果nums[i…j]不是重复字符串，j1>j，则nums[i…j1]不是重复字符串。故对每个i，只需要寻找最大不符合j。
性质三：如果nums[i…j]是重复字符串，则nums[i+1…j]也一定是重复子串。故i++后，j无需复位。故总时间复杂度是：O(n)。

代码

核心代码

class Solution {
		public:
			int maxRepOpt1(string text) {
				const int N = text.length();
				auto Do = [&](char ch) {
					int cnt = 0,ans=0;					
					for (int i = 0, j = 0; i < N; i++) {
						while ((j < N) && (cnt < 2 )) {
							cnt += (text[j] != ch); ++j;
						}
						if (N == j) {
							ans = max(ans,j - i);
						}
						else {
							ans =max(ans, j - 1 - i);
						}						
						cnt -= (text[i] != ch);
					}
					return min(ans,count(text.begin(),text.end(),ch));
				};
				int ans = 0;
				for (char ch = 'a'; ch <= 'z';ch++) {
					ans = max(ans, Do(ch));
				}
				return ans;
			}
		};

单元测试

string text;
		TEST_METHOD(TestMethod11)
		{
			text = "ababa";
			auto res = Solution().maxRepOpt1(text);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			text = "aaabaaa";
			auto res = Solution().maxRepOpt1(text);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod13)
		{
			text = "aaabbaaa";
			auto res = Solution().maxRepOpt1(text);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod14)
		{
			text = "aaaaa";
			auto res = Solution().maxRepOpt1(text);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod15)
		{
			text = "abcdef";
			auto res = Solution().maxRepOpt1(text);
			AssertEx(1, res);
		}