Advertisement
unknown_0711

Untitled

Oct 10th, 2022
830
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.67 KB | None | 0 0
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. public class Main
  6. {
  7.     public static void main (String[] args) throws java.lang.Exception
  8.     {
  9.       Scanner sc=new Scanner(System.in);
  10.       String s=sc.next();
  11.       String p=sc.next();
  12.       if(s.length()<p.length()){
  13.         System.out.print("-1");
  14.         return;
  15.       }
  16.       int n = s.length();
  17.       int m = p.length();
  18.       int pchar[] = new int[26];
  19.       for(int i =0; i < m; i++){
  20.         pchar[p.charAt(i)-'a']++;
  21.       }
  22.       int window[] = new int[26];
  23.       int i = 0;
  24.       int j = 0;
  25.       int ans = 1000000;
  26.       int index = 0;
  27.       while( j < n) {
  28.         window[s.charAt(j)-'a']++;
  29.         int flag = 1;
  30.         for(int k = 0; k < 26;k++) {
  31.              if(pchar[k] != 0 && window[k] == 0 ) {
  32.                flag = 0;
  33.                break;
  34.              }
  35.         }
  36.         if(flag  == 1) {
  37.          
  38.           while(true) {
  39.             //System.out.println(ans + " " + i + " " + j);
  40.               if(ans > j - i + 1) {
  41.               ans = j - i + 1;
  42.                // System.out.println(ans);
  43.               index = i;
  44.              }
  45.              if(pchar[s.charAt(i)-'a'] !=0 && window[s.charAt(i)-'a'] ==1) {
  46.                   window[s.charAt(i)-'a']--;
  47.                   i++;
  48.                   break;
  49.              }
  50.             else {
  51.                 window[s.charAt(i)-'a']--;
  52.             }
  53.             i++;
  54.             //System.out.println(i);
  55.         }
  56.          
  57.          
  58.         }
  59.         j++;
  60.       }
  61.       if(ans == 1000000) {
  62.         System.out.print("-1");
  63.       }
  64.       else {
  65.         System.out.print(s.substring(index,index + ans));
  66.       }
  67.  
  68.     }
  69. }
  70.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement