Smallest window in a string containing all the characters of another string

Given two strings s and t. Find the smallest substring in the string s consisting of all the characters(including duplicates) of the string t.

Return -1 in case there is no such substring present. In case there are multiple such windows of same length, return the one with the least starting index.

Input Format

First line contains string s.

Second line contains string t.

Output Format

Print an integer denoting the length of the smallest substring in s consisting of all the characters(including duplicates) of the string t.

Example 1

Input

timetopractice
toc

Output

toprac

Explanation

toprac is the smallest substring in which “toc” can be found.

Example 2

Input

zoomlazapzo
oza

Output

apzo

Explanation

apzo is the smallest substring in which “oza” can be found.

Constraints

1 <= |s|, |t| <= 10^5

Solution of Smallest window in a string containing all the characters of another string:–

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
        static boolean check(int[] a, int[] b){
    for(int i=0; i<26; i++){
      if(a[i] < b[i])return false;
    }
    return true;
  }
        
	public static void main (String[] args) throws java.lang.Exception
	{
		//your code here
              Scanner sc = new Scanner(System.in);
      String s = sc.next();
      String p = sc.next();
      int mp1[] = new int[26];
      int mp2[] = new int[26];
      if(s.length() < p.length()){
        System.out.println(-1);
        return;
      }
      for(int i=0; i<p.length(); i++){
        mp2[p.charAt(i)-'a']++;
        mp1[s.charAt(i)-'a']++;
      }
      if(check(mp1, mp2)){
        System.out.println(s.substring(0,p.length()));
        return;
      }
      int len = s.length()+1;
      String ans = "";
      int i=0, j=p.length()-1;
      while(i<j){
        while(!check(mp1, mp2) && j+1<s.length()){
          j++;
          mp1[s.charAt(j)-'a']++;
        }
        if(check(mp1, mp2) && j-i+1 < len){
          len = j-i+1;
          ans = s.substring(i, j+1);
        }
        mp1[s.charAt(i)-'a']--;
        i++;
      }
      if(len != s.length()+1){
        System.out.print(ans);
      }else System.out.println(-1);

	}
}