The brute force method would be calculate all the substrings, which would be inefficient.

Runtime Complexity *O(m + n)*

Space Complexity *O(m+n)*

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 | class Solution { public String minWindow(String s, String t) { int tLen = t.length(); int sLen = s.length(); if (tLen > sLen) return ""; int[] pattern = new int[256]; int[] given = new int[256]; for (int i = 0; i < tLen; i++) pattern[t.charAt(i)]++; int mstart = 0, size = 0, start = 0, min = sLen + 1; for (int j = 0; j < s.length(); j++) { char curr = s.charAt(j); if (given[curr] < pattern[curr]) size++; given[curr]++; if (size == tLen) { while (given[s.charAt(start)] > pattern[s.charAt(start)]) { given[s.charAt(start)]--; start++; } int len = j - start + 1; if (len < min) { min = len; mstart = start; } } } if (size < tLen) return ""; return s.substring(mstart, mstart + min); } } |