O(n) 5ms Java Solution Beats 93.18%
This solution adopts the idea described in this [LeetCode article][1]. It explains this O(n) solution very well. Because of that article, I kept the comments si
This solution adopts the idea described in this [LeetCode article][1]. 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.\n\n    public class Solution {\n      public String minWindow(String s, String t) {\n        char[] needToFind = new char[256];\n        char[] hasFound = new char[256];\n        int sLen = s.length();\n        int tLen = t.length();\n        int count = 0;\n        int optLen = Integer.MAX_VALUE; // opt stands for optimal\n        int optBegin = 0;\n        int optEnd = 0;\n        for (int i = 0; i < tLen; i++) { // gives a counter for each character in t\n          needToFind[t.charAt(i)]++;\n        }\n        for (int begin = 0, end = 0; end < sLen; end++) {\n          if (needToFind[s.charAt(end)] == 0) { // skips irrelevant char\n            continue;\n          }\n          char currEnd = s.charAt(end); // the char at the end\n          hasFound[currEnd]++;\n          if (hasFound[currEnd] <= needToFind[currEnd]) {\n            count++;\n          }\n          if (count == tLen) { // pauses end, moves beginning to the right as much as possible\n            char currBegin = s.charAt(begin); // char at begin\n            while (hasFound[currBegin] > needToFind[currBegin] || needToFind[currBegin] == 0) {\n              if (hasFound[currBegin] > needToFind[currBegin]) {\n                hasFound[currBegin]--;\n              }\n              begin++;\n              currBegin = s.charAt(begin);\n            }\n            if (optLen > end - begin + 1) { // if current length is smaller, update our optimum solution\n              optLen = end - begin + 1;\n              optBegin = begin;\n              optEnd = end;\n            }\n          }\n        }\n        if (count != tLen) {\n          return "";\n        }\n        return s.substring(optBegin, optEnd + 1);\n      }\n    }\n\n  [1]: http://articles.leetcode.com/finding-minimum-window-in-s-which/
['Java']