?LeetCode刷題實(shí)戰(zhàn)159：至多包含兩個(gè)不同字符的最長(zhǎng)子串

例 1:

輸入: “eceba”
輸出: 3
解釋: t 是 “ece”，長(zhǎng)度為3。

例 2:

輸入: “ccaabbb”
輸出: 5
解釋: t 是 “aabbb”，長(zhǎng)度為5。

class?Solution?{
????public?int?lengthOfLongestSubstringTwoDistinct(String s)?{

????????int?len = s.length();

????????//定義哈希表
????????int[] hashtable = new?int[128];
????????for?(int?i = 0; i < 128; i++){
????????????hashtable[i] = 0;
????????}

????????int?a = 0; //左指針
????????int?b = 0; //右指針
????????int?count = 0; //不同字符的個(gè)數(shù)
????????int?subLen = 0; //最長(zhǎng)子串的長(zhǎng)度
????????
????????//遍歷字符串
????????while?(b < len) {
????????????char?cb = s.charAt(b);
????????????//如果 b 處字符不存在于哈希表中
????????????if?(hashtable[hash(cb)] == 0){
????????????????count++; //不同字符個(gè)數(shù) +1
????????????}
????????????//哈希表對(duì)應(yīng)位置 +1
????????????hashtable[hash(cb)]++;
????????????
????????????//直到不同字符個(gè)數(shù) <= 2
????????????while?(count > 2){
????????????????char?ca = s.charAt(a);
????????????????hashtable[hash(ca)]--; //哈希表中 a 處字符對(duì)應(yīng)位置 -1
????????????????//如果哈希表中 a 處字符對(duì)應(yīng)位置不為 0
????????????????if?(hashtable[hash(ca)] == 0){
????????????????????count--; //不同字符個(gè)數(shù) -1
????????????????}
????????????????a++; //a指針右移
????????????}
????????????
????????????//計(jì)算子字符串長(zhǎng)度
????????????subLen = Math.max(subLen,b-a+1);
????????????b++;
????????}
????????return?subLen;
????}

????//定義哈希函數(shù)
????private?int?hash(char?c){
????????return?c;
????}
}

/**
?????* 解法一：采用滑動(dòng)窗口的算法思想，選取 left-right 子串進(jìn)行驗(yàn)證
?????* 如果字符數(shù)量沒有超過2，則記錄此時(shí)的最大長(zhǎng)度，并且 right++
?????* 如果字符數(shù)量超過2，則 left++
?????* 使用 map 存放出現(xiàn)過的字符及次數(shù)
?????*
?????* （優(yōu)化算法，使用數(shù)組替代 map)
?????*/
????public?int?lengthOfLongestSubstringTwoDistinct1(String s)?{
????????char[] chars = s.toCharArray();
????????int?len = chars.length;
????????Map map?= new?HashMap<>();
????????int?left = 0, right = 0;
????????int?count = 0;//不同的字符數(shù)量
????????int?maxLength = 0;
????????while?(right < len) {
????????????//在map中獲取該字符出現(xiàn)的次數(shù)(不存在則為0),次數(shù)+1
????????????int?rightNumber = map.getOrDefault(chars[right], 0) + 1;
????????????map.put(chars[right], rightNumber);//更新map
????????????if?(rightNumber == 1) {//第一次出現(xiàn)
????????????????count++;
????????????}
????????????right++;
????????????if?(count <= 2) {
????????????????maxLength = Math.max(maxLength, right - left);
????????????}
????????????while?(count > 2) {
????????????????//左側(cè)移除一個(gè)字符，在map中獲取該字符出現(xiàn)的次數(shù)-1
????????????????int?leftNumber = map.get(chars[left]) - 1;
????????????????map.put(chars[left], leftNumber);//更新map
????????????????if?(leftNumber == 0) {
????????????????????count--;
????????????????}
????????????????left++;
????????????}
????????}
????????return?maxLength;
????}

/**
?????* 最優(yōu)解
?????* 改進(jìn)1：考慮 ASCII 碼表中的128個(gè)字符，可以使用數(shù)組代替 map，存放每個(gè)字符出現(xiàn)的次數(shù)
?????* 改進(jìn)2：滑動(dòng)窗口 只會(huì)擴(kuò)大或者平移（我們要取的就是最大窗口長(zhǎng)度）
?????*
?????* @param s
?????* @return
?????*/
????public?int?lengthOfLongestSubstringTwoDistinct(String s)?{
????????final int?length = s.length();
????????final int[] map?= new?int[128];
????????int?right = 0, left = 0;
????????//count 為不同字符的數(shù)量
????????for?(int?count = 0; right < length; ) {
????????????//右側(cè)新字符進(jìn)入窗口
????????????if?(map[s.charAt(right++)]++ == 0) {
????????????????count++;
????????????}
????????????//如果新字符進(jìn)入窗口后使得 不同字符數(shù)量大于2，則左側(cè)窗口也向右滑動(dòng)一個(gè)（窗口平移）
????????????if?(count > 2) {
????????????????if?(--map[s.charAt(left++)] == 0) {
????????????????????count--;
????????????????}
????????????}
????????}
????????return?right - left;
????}