包含指定字符串的最小串-滑动窗口smallest substring which contains all characters from a given string
https://stackoverflow.com/questions/2459653/how-to-find-smallest-substring-which-contains-all-characters-from-a-given-string
import java.io.*; import java.util.*; class UserMainCode { public String GetSubString(String input1,String input2){ // Write code here... return find(input1, input2); } private static boolean containsPatternChar(int[] sCount, int[] pCount) { for(int i=0;i<256;i++) { if(pCount[i]>sCount[i]) return false; } return true; } public static String find(String s, String p) { if (p.length() > s.length()) return null; int[] pCount = new int[256]; int[] sCount = new int[256]; // Time: O(p.lenght) for(int i=0;i) { pCount[( int)(p.charAt(i))]++; sCount[(int)(s.charAt(i))]++; } int i = 0, j = p.length(), min = Integer.MAX_VALUE; String res = null; // Time: O(s.lenght) while (j < s.length()) { if (containsPatternChar(sCount, pCount)) { if ((j - i) < min) { min = j - i; res = s.substring(i, j); // This is the smallest possible substring. if(min==p.length()) break; // Reduce the window size. sCount[(int)(s.charAt(i))]--; i++; } } else { sCount[(int)(s.charAt(j))]++; // Increase the window size. j++; } } System.out.println(res); return res; } }