[leetcode] Minimum Window Substring

NO IMAGE

這裡聊一聊解一類問題,就是滿足某一條件的substring最值問題。
最開始我們以Minimum Window Substring為例,並整理總結leetcode裡所有類似題目的通解。

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
S = “ADOBECODEBANC” , T = “ABC”, Minimum window is “BANC”.

我們要把問題拆解成三個字問題:唯一的表示substring, 檢查substring是否符合要求,記錄最值。
1.
如何唯一的表示一個substring, 有兩種方法,一種用頭尾指標,一種用尾指標加substring長度。
2.
檢查substring是否符合要求,這道題目要求包含T中的每個字母,所以我們需要一個counter來記錄T裡每個character出現的次數,空間O(26) O(128) O(256) 都行, 可以和面試官討論。類似題目唯一變化的就是這個部分,可以是每個字元只能出現一次,最多出現兩個不同字元,每個字元最多出現K次等等。
3.
記錄最值。根據掃描方法的不同,長度有時為r-l,此時r不包含在substring裡,有時為r-l 1,此時包含在substring裡。

這篇部落格主要講第二個子問題,如何判斷substring是否符合要求。以Minimum Window Substring為例。

public class Solution {
public String minWindow(String s, String t) {
// empty check
if(s == null || t == null || s.length() == 0 || t.length() == 0) return "";
// initial counter for valid check
int[] counter = new int[128];
for(char c : t.toCharArray()){
counter[c]  ;
}
// variables help represent substring and min/max
char[] chs = s.toCharArray();
// 變數名解釋,i表示頭即先開始掃描的指標,j表示尾。i,j對counter的操作相反,一個加一個減或者一個減一個加。 
// 上面的counter記錄每個字元出現次數,count表示substring裡滿足條件的字元出現總次數(可以從0加到count,也可以從count減少到0.
int j = 0, i=0, minLen = Integer.MAX_VALUE, start = 0, count = t.length();
//這裡可以使用for和while兩種迴圈,個人偏向for, 因為i指標要一次走一個字元遍歷完整個string.
for( ; i < chs.length; i  ){      //逐個掃描
// 我們包含了第i個元素,並且要立即判斷是否滿足條件。使用--x, 而不是x--.
if(--counter[chs[i]] > -1) {
count--;
}
// 因為我們需要的是最值,中間值我們不在乎,所以一次收斂到最小。
while(count == 0) {     // 快速收緊
if(i -j   1< minLen) {
minLen = i - j   1;
start = j;
}
// 用 == 0 判斷是因為有的substring裡個別字元可能偏多,多餘的字元不會算作滿足條件。下方有簡單的例子。 
// 一次只移動一個char, 所以這裡用 == 0
if(counter[chs[j  ]]   == 0) {
count  ;
}
}
}
return minLen == Integer.MAX_VALUE ? "" : new String(chs, start, minLen);
}
}

X表示佔位符,不是字母X。(使用空格會被自動消除,所以這裡用了X)
S: ADOBECODEBANC T: ABC
i: ADOBECXXXXXXXX
j: XDOBECXXXXXXX
i: XDOBECODEBAXX
j: XXXXXXODEBAXX
注意這一步j最後落在了C後面,而不是B的後面。因為B在T裡只出現了一次, i在掃描的時候會減小兩次,counter[B] = -1, counter[c] = 0
i: XXXXXXODEBANC
j: XXXXXXXXXBANC

將S,T裡字元換成String,變成Leetcode 30, Substring with Concatenation of All Words.
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
s: “barfoothefoobarman”, words: [“foo”, “bar”], You should return the indices: [0,9]

字元長度為K,我們可能從0, 1, 2, K-1開始組成不同字元, 從K開始會和從O開始重合了。程式碼如下,不過多解釋,可以直接跳過。

public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
int N = s.length(), M = words.length, K = words[0].length();
// check input
if(s == null || K == 0 || N < M*K) return res;
Map<String, Integer> map = new HashMap<>(), curMap = new HashMap<>();
// initial counter
for(String word: words) {
map.put(word, map.getOrDefault(word,0)   1);
}
// str denote first word, temp denote last word
String str = null, temp = null;
for(int i=0; i< K; i  ) { 
int count = 0;
// two poniter scan, each time move K steps
for(int l=i, r=i; r K <= N; r  = K) {
str = s.substring(r, r K);
if(map.containsKey(str)) {
curMap.put(str, curMap.getOrDefault(str,0)   1);
if(curMap.get(str) <= map.get(str)) count  ;
// has a word above the counter of it
while(curMap.get(str) > map.get(str)) {
temp = s.substring(l, l K);
curMap.put(temp, curMap.get(temp) - 1);
l  = K;
if(curMap.get(temp) < map.get(temp)) count--;
}
// should be exactly M, when meet, delete last word
if(count == M){
res.add(l);
temp = s.substring(l, l K);
curMap.put(temp, curMap.get(temp) - 1);
l  = K;
count--;
}
} else {
curMap.clear();
count = 0;
l = r   K;
}
}
curMap.clear();
}
return res;
}
}

下面來三個longest substring.
LC3 Longest Substring Without Repeating Characters
需要查重並且記錄上次出現的位置,選擇map.
以abcdba為例,i走到b, 用map做檢查,發現出現過,把j移到map.get(b)的下一個。
i走到a, 用map做檢查,發現出現過,把j移到map.get(a)的下一個。發現不對,因為下一個字元是b已經出現過兩次,所以需要一個比較,取map.get(b),map.get(a)的最大值。

public class Solution {
public int lengthOfLongestSubstring(String s) {
// empty check
if(s == null || s.length() == 0) return 0;
// <char, last appear pos>
Map<Character, Integer> map = new HashMap<>();
// scan whole string and calculte
int len = 0;
char[] chs = s.toCharArray();
for(int i=0, j=0; i<chs.length; i  ) {
if(map.containsKey(chs[i])) {
j = Math.max(j, map.get(chs[i]) 1);  // abcdba, need to compare
}
map.put(chs[i], i);
if(i-j 1 > len) {
len = i-j 1;
}
}
return len;
}
}

LC340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is “ece” which its length is 3.

counter記錄每個字元出現次數。 count表示有多少個不同字元,題目要求最多出現k個。

public class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
// corner case
if(s== null || s.length() == 0)  return 0;
// counter, count denote k
int[] counter = new int[128];
// l denote tail, r denote head, two pointer scan
int j = 0, len = 0, count = 0;
for(int i=0; i<s.length(); i  ) {
// only denote first appearence
if(counter[s.charAt(i)]   == 0) {
count  ;
}
// at most k, // very important part
if(count > k) { 
while( --counter[s.charAt(j  )] > 0);   
count--;
}
if(i - j   1 > len) {
len = i - j  1;
}
}
// return max
return len;
}
}

LC159. Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s = “eceba”,
T is “ece” which its length is 3.

是上個題目的簡易版,或者特殊版。只有兩個字元,我們就不需要一個陣列了,只需要兩個位置標記就行。p1, p2. 為了讓計算最值方便,讓p1始終小於p2.

這裡需要注意的就是p1,p2在repeating characters出現的時候,同時會指向這個字串的最後一個。
在判斷第三個字元是否出現的時候,首先要比較p1 != p2.

public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if(s.isEmpty()) return 0;
int p1 = 0, p2 = 0, max = 1, len = 1; 
char[] chs = s.toCharArray();
for(int i=1; i<chs.length; i  ) {
if(p1 != p2 && chs[i] != chs[p1] && chs[i] != chs[p2]) {
if(len > max) max = len;
len = i - p1;       // always keep p1,p2 ordered p1<=p2
p1 = p2;
p2 = i;
} else {  
if(chs[i] == chs[p1]) {  // 0 or repeating charcters lead to p1=p2
p1 = p1 == p2 ? i:p2;
}
len  ;
p2 = i;
}
}
if (len > max) max = len;
return max;
}
}

今天先寫到這裡,以後補充。