Skip to content

Commit 9d7d6c8

Browse files
awangdevawangdev
committed
Minimum window substring
1 parent 7bf09db commit 9d7d6c8

File tree

6 files changed

+854
-629
lines changed

6 files changed

+854
-629
lines changed

‎Java/Change to Anagram.java

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
E
2+
3+
简单的check int[26] 26个小写字母是否需要改变。若需要count+1.
4+
5+
主要HackerRank里要注意自己写: Scanner, import java.util, non-static method ...etc.
6+
7+
注意: 最后count出来要除以2：字母不同，会在不同的字母位上加减count,那么就是刚好重复计算了一遍。所以除以二。
8+
9+
```
10+
/*
11+
HackerRank CodePair
12+
13+
Sid loves to read short stories. Being a Computer Science student, he decides to do some frequency analysis on his favorite reading material. For each data point, chooses a string of length a from one book, and a string of length b from a second book. The strings' lengths differ by no more than 1.
14+
|a-b|≤1, where |x| represents the absolute value function.
15+
16+
The frequency analysis consists of checking how far the strings are from being anagrams of one another. Your challenge is to help him find the minimum number of characters of the first string he needs to change to make it an anagram of the second string. He can neither add nor delete characters from the first string. Only replacement of the characters with new ones is allowed.
17+
18+
Input Format
19+
The first line will contain an integer T representing the number of test cases. Each test case will contain a string having length (a+b) which will be concatenation of both the strings described in problem. The string will only contain small letters and without any spaces.
20+
21+
Output Format
22+
An integer corresponding to each test case is printed in a different line i.e., the number of changes required for each test case. Print ‘-1’ if it is not possible.
23+
24+
Constraints
25+
1 ≤ T ≤ 100
26+
1 ≤ a+b ≤ 10,000
27+
28+
Sample Input
29+
5
30+
aaabbb
31+
ab
32+
abc
33+
mnop
34+
xyyx
35+
Sample Output
36+
3
37+
1
38+
-1
39+
2
40+
0
41+
42+
Explanation
43+
In the five test cases
44+
One string must be “aaa” and the other “bbb”. The lengths are a=3 and b=3, so the difference is less than 1. No characters are common between the strings, so all three must be changed.
45+
One string must be “a” and the second “b”. The lengths are a=1 and b=1, so the difference is less than 1. One character must be changed to them the same.
46+
Since the string lengths a and b must differ by no more than 1, the lengths are either a=1 and b=2 or a=2 and b=1. No sequence of substitutions will make the two anagrams of one another.
47+
One string must be “mn" and other be “op”. The length are a=2 and b=2, so the difference is less than 1. No characters are common between the strings, so both must be changed.
48+
One string must be “xy” and the other be “yx”. The length are a=2 and b=2, so the difference is less than 1. No changes are needed because the second string is already an anagram of the first.
49+
*/
50+
51+
52+
/*
53+
Check if they are valid string. If length == odd, then fail, -1
54+
Use int[26] arr to add chars from s1. If non-26-char exist, return -1
55+
use same int arr to remove chars from s2.
56+
count the non-zeros
57+
58+
Note: the order of letters does not matter, becase all we want to change to is anagram
59+
*/
60+
import java.io.*;
61+
import java.util.*;
62+
public class Solution {
63+
public static void main(String args[] ) throws Exception {
64+
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
65+
Scanner in = new Scanner(System.in);
66+
int numOfCase = Integer.parseInt(in.nextLine());
67+
Solution sol = new Solution();
68+
69+
while (numOfCase > 0) {
70+
int rst = sol.validate(in.nextLine());
71+
System.out.println(rst);
72+
numOfCase--;
73+
}
74+
}
75+
76+
public int validate(String str) {
77+
if (str.length() % 2 == 1) {
78+
return -1;
79+
}
80+
String sA = str.substring(0, str.length()/2);
81+
String sB = str.substring(str.length()/2);
82+
83+
int[] arr = new int[26];
84+
for (int i = 0; i < sA.length(); i++) {
85+
char cA = sA.charAt(i);
86+
char cB = sB.charAt(i);
87+
if (cA < 'a' || cA > 'z' || cB < 'a' || cB > 'z') {
88+
return -1;
89+
}
90+
arr[cA - 'a']++;
91+
arr[cB - 'a']--;
92+
}
93+
94+
int count = 0;
95+
for (int num : arr) {
96+
count += Math.abs(num);
97+
}
98+
return count/2;
99+
}
100+
101+
102+
}
103+
```

‎Java/Group Anagrams.java

100644100755
Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,8 @@
44

55
把所有anagram 存在一起。注意结尾Collections.sort().
66

7+
O(NKlog(K)), N = string[] length, k = longest word length
8+
79
```
810

911
/*

‎Java/Minimum Window Substring.java

Lines changed: 168 additions & 69 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,28 @@
1-
M
1+
H
22

3-
Need look again. Had bad solution at 2nd attempt.
3+
LeetCode Hard
4+
LintCode M, 测试有问题，即使做错也能过.
5+
6+
基本思想: 用个map存target的<char, int frequency>。 然后在搜索s的时候，遇到Match， frequency--.
7+
一旦map里面的frequency都被减为0, 就说明找到candidate.
8+
9+
有好几个trick：考虑start，前指针怎么移动；考虑start在candidate首字母没有多余前，不能移动；考虑candidate出现的情况...
10+
11+
复习时，回去看别人网站和自己的thoughts
412

513
```
614
/*
7-
Given a string source and a string target, find the minimum window in source which will contain all the characters in target.
15+
Given a string source and a string target, find the minimum window in source
16+
which will contain all the characters in target.
817
918
Example
1019
source = "ADOBECODEBANC" target = "ABC" Minimum window is "BANC".
1120
1221
Note
1322
If there is no such window in source that covers all characters in target, return the emtpy string "".
1423
15-
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in source.
24+
If there are multiple such windows, you are guaranteed that
25+
there will always be only one unique minimum window in source.
1626
1727
Challenge
1828
Can you do it in time complexity O(n) ?
@@ -26,8 +36,161 @@ Can you do it in time complexity O(n) ?
2636
Hash Table
2737
*/
2838

39+
/*
40+
03.09.2016
41+
http://blog.sina.com.cn/s/blog_eb52001d0102v2il.html
42+
43+
只利用一个hashmap save frequency of target.
44+
1. 从map里面 减去 source char match target char 的frequency. 如果发现frequency = 0, size++
45+
size == map.size,说明有一个candidate.
46+
2. 维持left,right pointer。
47+
记住一个规则: 如果map里面在left index上面的frequency >=0, 也就是frequency 没有小于0，所以暂时没有多余的这个char on left index.
48+
因此left不能动。这里要测试并且break。
49+
然而，当frequency < 0时候，说明在后续的String里面出现了多余的char,也就是frequency--使其小于0. 这里，我们就可以动left++了，并且frequency++。
50+
这个效果就等于，当matched char在后面有重复出现（多余）时，我们可以left++，安全移动。
51+
52+
另外. 其余那些不在target里面的char, 用left++过滤掉。
53+
54+
3. right pointer一直在按规律跑动。
55+
56+
4. 当size == map.size(), 截取string
57+
58+
*/
59+
public class Solution {
60+
public String minWindow(String s, String t) {
61+
if (s == null || s.length() == 0 || t == null || t.length() == 0) {
62+
return "";
63+
}
64+
//Init map based on t
65+
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
66+
for (int i = 0; i < t.length(); i++) {
67+
char c = t.charAt(i);
68+
if (!map.containsKey(c)) {
69+
map.put(c, 0);
70+
}
71+
map.put(c, map.get(c) + 1);
72+
}
73+
74+
int count = 0;
75+
int start = 0;
76+
int end = 0;
77+
int lengS = s.length();
78+
int leng = Integer.MAX_VALUE;
79+
String rst = "";
80+
//Iteratve through s
81+
for (; end < lengS; end++) {
82+
char c = s.charAt(end);
83+
if (map.containsKey(c)) {
84+
map.put(c, map.get(c) - 1);
85+
if (map.get(c) == 0) {
86+
count++;
87+
}
88+
}
89+
90+
while (start < lengS) {
91+
char cs = s.charAt(start);
92+
if (map.containsKey(cs)) {
93+
//If >= 0 still being used in map, not ready yet: can't move
94+
if (map.get(cs) >= 0) {
95+
break;
96+
} else {//less than 0, so we can skip previous cs, move start++
97+
map.put(cs, map.get(cs) + 1);
98+
}
99+
}
100+
//skip non-t chars
101+
start++;
102+
}
103+
104+
if (count == map.size() && (end - start + 1) < leng) {
105+
rst = s.substring(start, end + 1);
106+
leng = rst.length();
107+
}
108+
}//end for
109+
110+
return rst;
111+
}
112+
}
113+
114+
115+
116+
/*
117+
Same as below solution, incorrect: only picks the first possible solution, not minimum window.
118+
HOWEVER, it accidentally passed LintCode.
119+
120+
只能找到第一个, 所以有错。
121+
122+
//HashT<char, frequency>
123+
//HashS<char, frequency>: count the frequency of chars from source.
124+
//once found one candidate, we may have a large window. Now move left-most char by comparison using HashS, to minimize the window
125+
126+
*/
127+
public class Solution {
128+
public String minWindow(String s, String t) {
129+
if (s == null || s.length() == 0 || t == null || t.length() == 0) {
130+
return "";
131+
}
132+
133+
HashMap<Character, Integer> hashT = new HashMap<Character, Integer>();
134+
HashMap<Character, Integer> hashS = new HashMap<Character, Integer>();
135+
//init hashT
136+
for (int i = 0; i < t.length(); i++) {
137+
char c = t.charAt(i);
138+
if (!hashT.containsKey(c)) {
139+
hashT.put(c, 0);
140+
}
141+
hashT.put(c, hashT.get(c) + 1);
142+
}
143+
144+
//Check against S
145+
int count = 0;
146+
for (int i = 0; i < s.length(); i++) {
147+
char c = s.charAt(i);
148+
if (!hashT.containsKey(c)) {
149+
continue;
150+
}
151+
if (!hashS.containsKey(c)) {
152+
hashS.put(c, 0);
153+
}
154+
hashS.put(c, hashS.get(c) + 1);
155+
156+
if (hashS.get(c) <= hashT.get(c)) {
157+
count++;
158+
}
159+
160+
//Found string
161+
if (count == t.length()) {
162+
return findStr(i, s, hashT, hashS);
163+
}
164+
}
165+
return "";
166+
}
167+
168+
public String findStr(int end, String s,
169+
HashMap<Character, Integer> hashT, HashMap<Character, Integer> hashS) {
170+
int start = 0;
171+
while (start < s.length()) {
172+
char c = s.charAt(start);
173+
if (!hashS.containsKey(c)) {
174+
start++;
175+
continue;
176+
}
177+
if (hashS.get(c) > hashT.get(c)) {
178+
hashS.put(c, hashS.get(c) - 1);
179+
start++;
180+
continue;
181+
}
182+
break;
183+
}//end while
184+
185+
return s.substring(start, end + 1);
186+
}
187+
}
188+
189+
190+
29191

30192
/*
193+
Not working: it only picks up the first possible solution, but not the shortest
31194
Thoughts:
32195
The idea was from jiuzhang.com.
33196
1. count target Characters: store each Character with HashMap:tCounter<Character, # appearance>
@@ -46,12 +209,7 @@ srouce string and can also be used as head of the result string (with shorter le
46209
import java.util.*;
47210

48211
public class Solution {
49-
/**
50-
* @param source: A string
51-
* @param target: A string
52-
* @return: A string denote the minimum window
53-
* Return "" if there is no such a string
54-
*/
212+
55213
public String minWindow(String source, String target) {
56214
if (source == null || source.length() == 0) {
57215
return source;
@@ -120,63 +278,4 @@ public static void main(String[] args) {
120278
}
121279

122280

123-
124-
125-
/*
126-
3.2.2016, another thought. But this does not work.
127-
1. record hashmap<char, list of index of matched char>
128-
2. record matched char's indexes in a arraylsit
129-
3. Use a char[256] to check through the arraylist, if any sequence match target chars, then use the position to calculate a result.
130-
4. repeat 3 and find the minimum
131-
*/
132-
public class Solution {
133-
public String minWindow(String source, String target) {
134-
if (source == null || source.length() == 0 || target == null || target.length() == 0) {
135-
return "";
136-
}
137-
int[] match = new int[256];
138-
for (int i = 0; i < target.length(); i++) {
139-
match[target.charAt(i)] += 1;
140-
}
141-
142-
ArrayList<Integer> posList = new ArrayList<Integer>();
143-
for (int i = 0; i < source.length(); i++) {
144-
if (target.indexOf(source.charAt(i)) != -1) {
145-
posList.add(i);
146-
}
147-
}
148-
149-
int[] arr = new int[256];
150-
String matchStr = Arrays.toString(match);
151-
String rst = "";
152-
int start = -1;
153-
int end = -1;
154-
for (int i = 0; i < posList.size(); i++) {
155-
int pos = posList.get(i);
156-
char c = source.charAt(pos);
157-
if (target.indexOf(c) != -1) {
158-
if (arr[c] < match[c]) {
159-
arr[c] += 1;
160-
}
161-
162-
if (start == -1) {
163-
start = pos;
164-
}
165-
}
166-
167-
if (Arrays.toString(arr).equals(matchStr)) {
168-
end = posList.get(i);
169-
String temp = source.substring(start, end + 1);
170-
if (rst.length() == 0 || temp.length() < rst.length()) {
171-
rst = temp;
172-
}
173-
arr[start] -= 1;
174-
start = -1;
175-
}
176-
}//end for
177-
178-
return rst;
179-
}
180-
}
181-
182281
```

0 commit comments

Comments
 (0)