# O(n) 5ms Java Solution Beats 93.18%

• This solution adopts the idea described in this LeetCode article. It explains this O(n) solution very well. Because of that article, I kept the comments simple. I highly suggest you to read it before trying this code.

``````public class Solution {
public String minWindow(String s, String t) {
char[] needToFind = new char[256];
char[] hasFound = new char[256];
int sLen = s.length();
int tLen = t.length();
int count = 0;
int optLen = Integer.MAX_VALUE; // opt stands for optimal
int optBegin = 0;
int optEnd = 0;
for (int i = 0; i < tLen; i++) { // gives a counter for each character in t
needToFind[t.charAt(i)]++;
}
for (int begin = 0, end = 0; end < sLen; end++) {
if (needToFind[s.charAt(end)] == 0) { // skips irrelevant char
continue;
}
char currEnd = s.charAt(end); // the char at the end
hasFound[currEnd]++;
if (hasFound[currEnd] <= needToFind[currEnd]) {
count++;
}
if (count == tLen) { // pauses end, moves beginning to the right as much as possible
char currBegin = s.charAt(begin); // char at begin
while (hasFound[currBegin] > needToFind[currBegin] || needToFind[currBegin] == 0) {
if (hasFound[currBegin] > needToFind[currBegin]) {
hasFound[currBegin]--;
}
begin++;
currBegin = s.charAt(begin);
}
if (optLen > end - begin + 1) { // if current length is smaller, update our optimum solution
optLen = end - begin + 1;
optBegin = begin;
optEnd = end;
}
}
}
if (count != tLen) {
return "";
}
return s.substring(optBegin, optEnd + 1);
}
}
``````

• Can you tell me how can I pint the content of needToFind & hasFound char array. I want to see what it looks like actually,
because when I trued to print this array...

at line 18 I am trying to print but getting nothing there for my string ["S = ADOBECODEBANC"; t= "ABC"]

``````  char currEnd = s.charAt(end); // the char at the end
System.out.println(" Frequency of Char "  + currEnd + " is " + hasFound[currEnd]) ;
``````

Frequency of Char A is 
Frequency of Char B is 
Frequency of Char C is 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.