You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters. For example, given: S: “barfoothefoobarman” L: [“foo”, “bar”] You should return the indices: [0,9]. (order does not matter).
Brute Force Solution
Two Hashmaps
rest: store all words in L, including times of appreance
found: renew at each round, store matched words, including times of appreance
Two pointers
i: starting index of current substring
j: numebers of words matched to current substring
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public ArrayList<Integer> findSubstring(String S, String[] L) {
outer loop: i increment wordlen times, each time scan through S
inner loop: j increment wordlen per time, until first letter of last word
each outerloop: reset count=0, reset index=i
each innerloop: curdict to store current window
If tmp str not found in dict, increment index, reset count and curdict If found, add to curdict, count++ before count++: compare num, if exceeded, increment index ,then decrement count and curdict If count equals listlen add index into result, increment index, update curdict
//check each word to tell if it existes in give dictionary
if(!dict.containsKey(curWord)){
curdict.clear();
count = 0;
index = j + wordLen;
}else{
//form current dictionary
if(!curdict.containsKey(curWord))
curdict.put(curWord, 1);
else
curdict.put(curWord, curdict.get(curWord) + 1);
//count for current found word and check if it exceed given word count
if(curdict.get(curWord) <= dict.get(curWord)){
count++;
}else{
while(curdict.get(curWord) > dict.get(curWord)){
String temp = S.substring(index, index + wordLen);
curdict.put(temp, curdict.get(temp)-1);
index = index + wordLen;//make index move next
if(curdict.get(temp)<dict.get(temp))
count--;
}
}
//put into res and move index point to nextword
//and update current dictionary as well as count num
if(count == L.length){
res.add(index);
String temp = S.substring(index, index + wordLen);
curdict.put(temp, curdict.get(temp)-1);
index = index + wordLen;
count--;
}
}
}//end for j
}//end for i
return res;
}
Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
Brute force method
Find all substrings and check if each of it contains only unique characters. As for the maxlength, we use Greedy Algorithm to only keep the longest substring seen so far. There are one inner loop and each check takes linear time, O(N^2) time won’t pass the OJ.
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). For example, S = “ADOBECODEBANC” T = “ABC” Minimum window is “BANC”. Note: If there is no such window in S that covers all characters in T, return the emtpy string “”. If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
Use a Hashmap to record each character, numbers in T
Two pointers:
left: increment when current substring contains all chars in T, pass unrelevant chars and exceeded chars right: increment each loop, if found a match in T decrement its Hashmap value
Minlen: when we found a new substring update minlength
HashMap<Character, Integer> dict = new HashMap<>();
for (int i = 0; i < T.length(); i++) {
char c = T.charAt(i);
if (!dict.containsKey(c))
dict.put(c, 1);
else
dict.put(c, dict.get(c) + 1);
}
HashMap<Character, Integer> found = new HashMap<>();
int foundCounter = 0;
int start = 0;
int end = 0;
int min = Integer.MAX_VALUE;
String minWindow = "";
while (end < S.length()) {
char c = S.charAt(end);
if (dict.containsKey(c)) {
if (found.containsKey(c)) {
if (found.get(c) < dict.get(c))
foundCounter++;
found.put(c, found.get(c) + 1);
} else {
found.put(c, 1);
foundCounter++;
}
}
if (foundCounter == T.length()) {
//When foundCounter equals to T.length(), in other words, found all characters.
char sc = S.charAt(start);
while (!found.containsKey(sc) || found.get(sc) > dict.get(sc)) {
if (found.containsKey(sc) && found.get(sc) > dict.get(sc))
found.put(sc, found.get(sc) - 1);
start++;
sc = S.charAt(start);
}
if (end - start + 1 < min) {
minWindow = S.substring(start, end + 1);
min = end - start + 1;
}
}
end++;
}
return minWindow;
}
Array Solution
To count occurrence of characters, instead of using a hash map, can use an int array of 256 Two pointer method with one point to end and one point to start. Pointer advance condition: move end forward till finds one window, then move start forward till the window no longer valid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String minWindow(String S, String T) {
int[] map=newint[256],found=newint[256];
int start=0, count=0,end=0,minlen=S.length()+1,tlen=T.length(),slen=S.length();
if(end-start+1<minlen) {minlen=end-start+1; min = S.substring(start, end+1);
}
found[S.charAt(start)]--;
start++;
count--;
}
}
return min;
}
Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Brute Force Solution
Find all possible substrings and check if each is palindrome. O(N^3) too LTE…
