3. 無重復(fù)字符的最長子串
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max = 0;
int left = 0;
for(int i = 0; i < s.length(); i ++){
if(map.containsKey(s.charAt(i))){
left = Math.max(left,map.get(s.charAt(i)) + 1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-left+1);
}
return max;
}
}
76.最小覆蓋子串
給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 袄膏。
注意：
- 對于
t中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于t中該字符數(shù)量掺冠。 - 如果
s中存在這樣的子串沉馆，我們保證它是唯一的答案。
輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"
class Solution {
public String minWindow(String s, String t) {
if (s == null || s.length() == 0 || t == null || t.length() == 0){
return "";
}
int[] need = new int[128];
//記錄需要的字符的個數(shù)
for (int i = 0; i < t.length(); i++) {
need[t.charAt(i)]++;
}
//l是當(dāng)前左邊界德崭，r是當(dāng)前右邊界斥黑，size記錄窗口大小，count是需求的字符個數(shù)眉厨，start是最小覆蓋串開始的index
int l = 0, r = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;
//遍歷所有字符
while (r < s.length()) {
char c = s.charAt(r);
if (need[c] > 0) {//需要字符c
count--;
}
need[c]--;//把右邊的字符加入窗口
if (count == 0) {//窗口中已經(jīng)包含所有字符
while (l < r && need[s.charAt(l)] < 0) {
need[s.charAt(l)]++;//釋放右邊移動出窗口的字符
l++;//指針右移
}
if (r - l + 1 < size) {//不能右移時(shí)候挑戰(zhàn)最小窗口大小锌奴，更新最小窗口開始的start
size = r - l + 1;
start = l;//記錄下最小值時(shí)候的開始位置，最后返回覆蓋串時(shí)候會用到
}
//l向右移動后窗口肯定不能滿足了 重新開始循環(huán)
need[s.charAt(l)]++;
l++;
count++;
}
r++;
}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}
}
// python寫法
class Solution:
def minWindow(self, s: 'str', t: 'str') -> 'str':
from collections import defaultdict
lookup = defaultdict(int)
for c in t:
lookup[c] += 1
start = 0
end = 0
min_len = float("inf")
counter = len(t)
res = ""
while end < len(s):
if lookup[s[end]] > 0:
counter -= 1
lookup[s[end]] -= 1
end += 1
while counter == 0:
if min_len > end - start:
min_len = end - start
res = s[start:end]
if lookup[s[start]] == 0:
counter += 1
lookup[s[start]] += 1
start += 1
return res
159. 至多包含兩個不同字符的最長子串
給定一個字符串 s 憾股，找出 至多 包含兩個不同字符的最長子串 t 鹿蜀。
示例 1:
輸入: "eceba"
輸出: 3
解釋: t 是 "ece"，長度為3服球。
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
from collections import defaultdict
lookup = defaultdict(int)
start = 0
end = 0
max_len = 0
counter = 0
while end < len(s):
if lookup[s[end]] == 0:
counter += 1
lookup[s[end]] += 1
end +=1
while counter > 2:
if lookup[s[start]] == 1:
counter -= 1
lookup[s[start]] -= 1
start += 1
max_len = max(max_len, end - start)
return max_len
340. 至多包含 K 個不同字符的最長子串
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
from collections import defaultdict
lookup = defaultdict(int)
start = 0
end = 0
max_len = 0
counter = 0
while end < len(s):
if lookup[s[end]] == 0:
counter += 1
lookup[s[end]] += 1
end += 1
while counter > k:
if lookup[s[start]] == 1:
counter -= 1
lookup[s[start]] -= 1
start += 1
max_len = max(max_len, end - start)
return max_len
