Given a string s, return the maximum length of a substring such that it contains at most two occurrences of each character.
Example 1:
Input: s = "bcbbbcba"
Output: 4
Explanation:
The following substring has a length of 4 and contains at most two occurrences of each character: "bcbbbcba".
Example 2:
Input: s = "aaaa"
Output: 2
Explanation:
The following substring has a length of 2 and contains at most two occurrences of each character: "aaaa".
Constraints:
2 <= s.length <= 100
s consists only of lowercase English letters.
每个字符最多出现两次的最长子字符串。
给你一个字符串 s ,请找出满足每个字符最多出现两次的最长子字符串,并返回该子字符串的 最大 长度。
思路
这道题不难看出是用滑动窗口的思路,而且这道题很像159题。这道题左指针的移动条件是只要某个字母的出现次数大于2,就移动左指针。其余思路同一般滑动窗口题。
复杂度
时间O(n)
空间O(1)
代码
Java实现
class Solution {
public int maximumLengthSubstring(String s) {
int start = 0;
int end = 0;
int[] map = new int[256];
int res = 0;
while (end < s.length()) {
char c1 = s.charAt(end);
end++;
map[c1]++;
// 如果某个字母的出现次数大于2,就移动左指针
while (map[c1] > 2) {
char c2 = s.charAt(start);
start++;
map[c2]--;
}
res = Math.max(res, end - start);
}
return res;
}
}
标签:map,end,int,res,Two,Maximum,Substring,start,length
From: https://www.cnblogs.com/cnoodle/p/18537831