Smallest substring which contains all characters of other String

Find the smallest substring which contains all the characters of the other string. Here the characters order can be anything and only the conditions which need to be

  • All the characters of 2nd string should present the the substring
  • Substring should be with least window size.


Smallest Window
SAMPLE:


Input :  string = "this is a test string"
        pattern = "tist"

Output :  Minimum window is "t stri"
Explanation: "t stri" contains all the characters of pattern.

Input :  string = "geeksforgeeks"
        pattern = "ork" 

Output :  Minimum window is "ksfor"


Lets see simple program to get Smallest substring which contains all characters of other String


public class SmallestWindow {

 public static void main(String[] args) {
  
  String sen = "this is a test string";
  String sStr = "tist";
  int sStrLen = sStr.length();
  String smallSubString = null;
  
  for(int i=0;i<sen.length();i++) {
   for(int j=sStrLen-1;j<sen.length();j++) {
    String tmp = sen.substring(i, j+1);
    boolean isContains = isContains(tmp, sStr);
    if(isContains) {
     if(smallSubString == null) 
       smallSubString = tmp;
     else if(smallSubString.length() > tmp.length()) 
       smallSubString = tmp;
    }
   }
   sStrLen++;
  }
  if(smallSubString == null)
   System.out.println("No such window exists");
  else
   System.out.println("Smallest window ::: "+smallSubString);
 }
 
 public static boolean isContains(String tmp, String sStr) {
  
  int array[] = new int[256];
  
  for(int i=0;i<tmp.length();i++) {
   array[tmp.charAt(i)]++;
  }
  
  for(int i=0;i<sStr.length();i++) {
   if(array[sStr.charAt(i)] == 0) 
    return false;
   else 
    array[sStr.charAt(i)]--;
  }
  return true;
 }
}



OUTPUT:


Smallest window ::: t stri

No comments :

Post a Comment