-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathProblem76.java
More file actions
94 lines (73 loc) · 2.44 KB
/
Problem76.java
File metadata and controls
94 lines (73 loc) · 2.44 KB
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package com.leetcode.problems;
/*
76. Minimum Window Substring
Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".
Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Example 2:
Input: s = "a", t = "a"
Output: "a"
*
* */
import com.leetcode.utils.ReadFile;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
class Solution76 {
public String minWindow(String s, String t) {
if(s.length()<t.length())
{
return "";
}
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0, start = 0, len = Integer.MAX_VALUE,valid = 0;
for (int i = 0; i < t.length(); i++) {
need.put(t.charAt(i), 1+need.getOrDefault(t.charAt(i),0));
}
while (right<s.length())
{
char c = s.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c, 1 + window.getOrDefault(c, 0));
if(window.get(c).equals(need.get(c)))
{
valid++;
}
}
while (valid==need.size()){
if(right-left<len){
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
if(need.containsKey(d)){
if(need.get(d).equals(window.get(d))){
valid--;
}
window.put(d,window.get(d)-1);
}
}
}
System.out.println(start);
System.out.println(len);
return len==Integer.MAX_VALUE?"":s.substring(start, start+len);
}
}
public class Problem76 {
public static void main(String[] args) throws IOException {
Solution76 s = new Solution76();
String s2 = ReadFile.readFile("s.txt");
String s3 = ReadFile.readFile("t.txt");
String s1 = s.minWindow(s2, s3);
System.out.println(s1);
Integer a=12121212;
Integer b= 12121212;
System.out.println(a==b);
System.out.println(a.equals(b));
}
}