/*
Online Java - IDE, Code Editor, Compiler

Online Java is a quick and easy tool that helps you to build, compile, test your programs online.
*/

//MY NEW DEFINED REQUIREMENT => Find the smallest window (in String s) which contains all letters of permutations of String p 
//in that EXACT ORDER. AS REMINDER, we are choosing exact ORDER since it will otherwise just become an anagram exercise and 
//pointless selecting permutations.
// I also performed largest window as an extension
               
//From this requirement, checking objectives would be as follows:
//Presented String p appears in String s in that order within block size of String p
//Permutation of arrangment (String p) appears in String s in that ORDER (within block size of String p). 
//This scenario will cover the one above.
//Presented String p appears in String s in that order but fragmented within String s. Performing this operation by indexing 
//from each applicable location on String s.   
//Permutation of arrangment (String p) appears in String s in that order but fragmented. Performing this operation by indexing 
//from each applicable location on String s. This scenario will cover one above.</p>



import java.util.*;
import java.math.BigInteger;

//These are the values when performing compareTo() on BigIntegers        
//1: when the first BigDecimal is greater than the second BigDecimal.
//0: when the first BigDecimal is equal to the second BigDecimal.
//-1: when the first BigDecimal is less than the second BigDecimal.

public class Main 
{
    static BigInteger permutations;
    
    static int row;
    static int col;
    static int lastIndexLocationStringS;
    static int firstIndexLocationStringS;
    
    //we will never be sure on suitable rows since it depends on String s and String p
    static String [][]store = new String[1000][4];
    
    static int minimumWindow;
    static int maximumWindow;
    
    public static void main(String[] args) 
    {
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
        
        Map <Character, Integer> mp = new HashMap<Character, Integer>();
        
        //AS PER THE CHALLENGE**********
        //String p = "abc";
        //String s = "adobecodebanc";
        
        //TEST CASE 1: findPermutations("cbaebabacd","abc");
        //String p="abc";
        //String s="cbaebabacd";
        
        //TEST CASE 2:  findPermutations("abab","ab");
        //String p = "ab";
        //String s = "abab";
        
        //TEST CASE 3: findPermutations("azazazazazazzzzaaazazazaz", "az")
        //String p = "az";
        //String s = "azazazazazazzzzaaazazazaz";
        
        //TEST CASE 4: findPermutations("azazazazazazzzzaaazazazpp", "az");
        //String p = "az";
        //String s = "azazazazazazzzzaaazazazpp";
        
        //SHOWS CODE PASSING
        //TEST CASE 5: findPermutations("abcbcacab", "abc");
        //String p = "abcc";
        //String s = "abcde";
        
        //PASS
        //String p = "abccddd";
        //String s = "cabccdde";
        
        //String p = "aaaabccc";
        //String s = "abcdefgaaa";
        
        //FAIL
        //String p = "aaaabccc";
        //String s = "abcdefgaaa";
        
        //FAIL
        //String p = "aaabb";
        //String s = "abcdef";
        
        //String p = "a";
        //String s = "a";
	
	    //String p = "abcc";
 	    //String s = "abccab";        
        
        String p = "aabcdefghi";
        String s = "abcdefghijkabcdefghij";
        
        //String s  = "abcdabead";
        //String p="abd";
        
        //String s  = "amcdaibaxf";
        //String p="abdho";
        
        //String p = "aabbb";
        //String s = "abcdef";
        
        //String s  = "abcdabead";
        //String p="abd";
        
        int originalNumber=p.length();
        
        int n;
        int r = p.length();
        
        minimumWindow=s.length();
        
        maximumWindow=0;
        
        Map <Integer, BigInteger> m = new HashMap<>();
        
        Permutation perm = new Permutation();
        n=originalNumber;
        
        System.out.println("This is String(s): " + s);
        System.out.println("This is String(p): " + p);
        
        perm.Permutations (n,r,originalNumber, m);
        
        permutations = perm.getPermutations(p);
        System.out.println(permutations);
        
        perm.getPermutationsWithRepetitions(p,mp);
       
        if (perm.hasRepeatRvalues())
        {
            perm.getPermutationsWithRepetitionsCalculator(permutations,p);
            permutations = perm.getFinalPermutationsRepetitions();
            System.out.println("= " + permutations);
        }
       
        //Method call
        System.out.println("\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^FINDING PERMUTATION IN STRING S");
        findPermutations(s,p);
    }
    
    public static void findPermutations(String s, String p)
    {
        String output=null;
        String outputBackup=null;
        
        String outputMinimum=null;
        String outputMinimumBackup=null;
        
        String outputMaximum=null;
        String outputMaximumBackup=null;
        
        String maxOrMin="";
        
        boolean hasSufficientCharactersStringS=true;
        boolean hasIncompleteLettersInStringS=false;
        Set <Integer> stRandomNums = new HashSet<>();
        int pos=0;
        int subsetNumber=1;
        Set <String> st = new HashSet<>();
        StringBuilder sb = new StringBuilder(p);
        int startPos=0;
        boolean hasCharFound=false;
        int counter=0;
        StringJoiner sj;
        int temp1;
        Random rand = new Random();
        String[] valuesSet; 
        String []backupValuesSetBeforeModification;
        int num;
        int count=0;
        int subsetEntry=1;
        int cycles=0;
        int totalcycles=0;
        
        BigInteger difference= new BigInteger("0");
        
        List <String> backupValuesSet = new ArrayList<>();
        int currentSetSize;
        BigInteger newSetSize = new BigInteger("0");
        int n;
        
        //System.out.println("String (s) to search in: " + s);
        //System.out.println("String (p) template word: " + p);
        hasSufficientCharactersStringS=true;
        
        if (s.length()<p.length())
        {
            System.out.println("template word is longer length than main String");
            System.exit(0);
        }
        
        System.out.println("*************INITIAL VALUE OF  CYCLES: " + cycles);
        
        do
        {
            sj=new StringJoiner("");
            
            for (int m=0;m<p.length();m++)
            {
                temp1 = rand.nextInt(p.length());
                currentSetSize=stRandomNums.size();
                stRandomNums.add(temp1);
                
                if (m==0)
                {
                    sj.add(Character.toString(p.charAt(temp1)));
                }
                else
                {
                    if (stRandomNums.size()==currentSetSize)
                    {
                        //System.out.println("repeat random number: " + temp1);
                        m=m-1;
                    }
                    else
                    {
                        //System.out.println("random num: " + temp1);
                        sj.add(Character.toString(p.charAt(temp1)));
                    }
                }
            }
            
            stRandomNums.clear();
            currentSetSize=st.size();
            
            st.add(sj.toString());
            
	        newSetSize = new BigInteger(String.valueOf(st.size()));
	        
	        //THIS IS NEW CODE, IT CAN BE USED BY END USER TO GET ACCOUNTABILITY OF THE SET SIZE AT CERTAIN INTERVALS.
            //NOTE IT WILL HAVE HIT ON THE PERFORMANCE

            if (newSetSize.mod(new BigInteger("200000")).compareTo(new BigInteger("0"))==0) 
            //&& */newSetSize.compareTo(new BigInteger("999"))==1)
            {
                System.out.println("Attempting to add: " + sj +  " into the set (MAX permutations: " + permutations 
                + "\t(CURRENT: " + currentSetSize + "   NEW SIZE: " + newSetSize+"  CYCLES: " + cycles+ ")");
            }
            
            sj=new StringJoiner("");
                
            cycles++;
            totalcycles++;
        
        }while(newSetSize.compareTo(permutations)==-1);

        valuesSet = st.toArray(new String[st.size()]);
        backupValuesSetBeforeModification = st.toArray(new String[st.size()]);
        
        System.out.println("******************Contents of the backup set");
        System.out.println("******************Contents of the valuesSet");
        
        for (String g: valuesSet)
        {
            //System.out.println("Subset " + subsetNumber+": " + g);
            subsetNumber++;
        }
        subsetNumber=1;

        System.out.println("*************NEW VALUE CYCLES: " + cycles);
        System.out.println("*************RUNNING TOTAL CYCLES: " + totalcycles);
        
        System.out.println("***PROCESSING SET AT INDEX: " + (difference));
        System.out.println("**ENDING AT INDEX:***** " + st.size() +"\n");
        
        backupValuesSet= new ArrayList<>(Arrays.asList(backupValuesSetBeforeModification)); 
        
        for (int entry=0; entry<valuesSet.length; entry++)
        {
            if (valuesSet[entry]!="ALREADY PROCESSED")
            {
                //System.out.println("\n\n"+valuesSet[entry] + "\t\tSubset: " + subsetEntry  + "  at cycle number: " + totalcycles);
                //System.out.println("String s: " + s);
                subsetEntry++;
            
                sb=new StringBuilder(valuesSet[entry]);
                
                //System.out.println("String (s) to search in: " + s);
                //System.out.println("String (p) template permutation word: " + sb);
                
                hasSufficientCharactersStringS=true;
                
                do
                {
                    do
                    {
                        startPos=counter;
                        
                         if (hasSufficientCharactersStringS)
                         {
                        
                            for (int i=startPos; i<s.length();i++)
                            {
                                if(sb.toString().length()>(s.length()-i))
				                {
				                    //System.out.println("Insufficient characters in String s");
				                    //System.out.println("FOLLOWING LETTERS NOT MATCHED: " + sb);
				                    
				                    hasSufficientCharactersStringS = false;
                                    sb.delete(0,sb.length());
                                }
                            
                                if (!sb.toString().isEmpty())
                                {
                                    //System.out.println("Checking character: " + sb.toString().charAt(pos) + 
                                    //"  against the main String index: " + i + "("+s.charAt(i)+")");
                                
                                    //System.out.println("SUBSTRING EXAMINED: " + s.substring(startPos,s.length()));
				                        
				                    if (hasSufficientCharactersStringS)
				                    {
				                        if (Character.toString(s.charAt(i)).indexOf(sb.toString().charAt(pos))==0)
				                        {
				                            //System.out.println("char found: " + sb.toString().charAt(pos) + "    at index: " + i);
				                      
				                            lastIndexLocationStringS=i;
				                        
				                            //System.out.println(sb.toString().charAt(pos) + " has been removed from StringBuilder (String p)" +  "= "+ sb.toString());
                                            sb.deleteCharAt(pos);
                                            //System.out.println("This is current StringBuilder (String p): " + sb.toString());
                                            hasCharFound=true;
                                        
                                            if (sb.length()==p.length()-1)
                                            {
                                                firstIndexLocationStringS=i;
                                            }
                                        }
				                    }
                                
                                    if (hasSufficientCharactersStringS)
				                    {
				                        if (!sb.toString().isEmpty() && (i==s.length()-1))
                                        {
                                            if (sb.length()==p.length())
                                            {
                                                if (entry==0)
                                                {
                                                    System.out.println("********NO CHARACTERS FROM PERMUTATION TEMPLATE WORD ARE FOUND IN STRING S********");
                                                }
                                            }
                                            //System.out.println("FOLLOWING LETTERS NOT MATCHED: " + sb);
                                            //System.out.println("StringBuilder being emptied: " + sb.toString());
                                            sb.delete(0,sb.length());
                                            hasCharFound=false;
                                    
                                            hasIncompleteLettersInStringS=true;
                                            break;
                                        }
                                    }
                                }
                            }
                        }
                        
                    }while(!sb.toString().isEmpty());
        
                    if (sb.toString().isEmpty() && hasCharFound && !hasIncompleteLettersInStringS && hasSufficientCharactersStringS)
                    {
                        System.out.println("**********************************************************");
                        System.out.println(s.substring(startPos,(lastIndexLocationStringS+1)) 
                        + " is a substring containing characters matching permutation: " + valuesSet[entry]  + "\t\t\tIndex("+startPos+")");
                        System.out.println("**********************************************************");
                        
                        
                        //System.out.println("String p (all characters) found within window ("+ (lastIndexLocationStringS-(firstIndexLocationStringS)+1) + ")"    
                        //+  ": \tString s (index: " + firstIndexLocationStringS+" - " + lastIndexLocationStringS+")");
                        
                        if(lastIndexLocationStringS-startPos>=p.length())
                        {
                            //System.out.println("----STORING WINDOW RESULT (MINIMUM): " +s.substring(startPos,(lastIndexLocationStringS+1)) 
                            //+ " (Index: " + firstIndexLocationStringS + "-" + lastIndexLocationStringS + "  Window: " + (lastIndexLocationStringS-firstIndexLocationStringS+1)+")" + "  String p: " + valuesSet[entry]);
                            
                            store[row][col]=String.valueOf(firstIndexLocationStringS);
                            store[row][col+1]=String.valueOf(lastIndexLocationStringS);
                            store[row][col+2]=valuesSet[entry];
                            store[row][col+3]="MINIMUM";
                            row++;
                            
                            //System.out.println("----STORING WINDOW RESULT (MAXIMUM): " +s.substring(startPos,(lastIndexLocationStringS+1)) 
                            //+ " (Index: " + firstIndexLocationStringS + "-" + lastIndexLocationStringS + "  Window: " + (lastIndexLocationStringS-firstIndexLocationStringS+1)+")" + "  String p: " + valuesSet[entry]);
                            
                            store[row][col]=String.valueOf(firstIndexLocationStringS);
                            store[row][col+1]=String.valueOf(lastIndexLocationStringS);
                            store[row][col+2]=valuesSet[entry];
                            store[row][col+3]="MAXIMUM";
                            row++;
                        }
                    }
		            if (sb.toString().isEmpty() && !hasCharFound && hasIncompleteLettersInStringS)
                    {
                        System.out.println("**********************************************************");
                        System.out.println(s.substring(startPos) + " is NOT a substring containing characters matching permutation:: " + valuesSet[entry] 
                        + "\t\t\tIndex("+counter+")");
                        System.out.println("**********************************************************");
                    }
                    //System.out.println("*****RESTORING BACKUP OF STRINGBUILDER (String p): " + valuesSet[entry]);
                    
                    sb=new StringBuilder(valuesSet[entry]);
                    hasCharFound=false;
                    hasIncompleteLettersInStringS=false;
                    firstIndexLocationStringS=0;
                    firstIndexLocationStringS=0;
                    counter++;
            
                }while(p.length()+startPos<s.length()  && hasSufficientCharactersStringS);

                counter=0;
                startPos=0;
            }
        }
        
        System.out.println("\n\n-----------String s: " + s + "\tString p: " + p + "\tMinimum window: " + minimumWindow + "\tMaximum window: " + maximumWindow);                
        System.out.println("\n\n------------All Windows: String p in String s");

        
        for (int c=0; c<row; c++)
        {
            firstIndexLocationStringS = Integer.valueOf(store[c][col]);
            lastIndexLocationStringS = Integer.valueOf(store[c][col+1]);
            
            output = 
            s.substring(firstIndexLocationStringS,(lastIndexLocationStringS+1)) 
            + " index(" +firstIndexLocationStringS+"-"+lastIndexLocationStringS+") is a substring containing characters matching permutation: " 
            + store[c][col+2] + "("+maxOrMin + "   Window size: " + (lastIndexLocationStringS-(firstIndexLocationStringS)+1)+")";   
                    
            try
            {
                if (!outputBackup.equals(output))
                {
                        maxOrMin=store[c][col+3];
                        System.out.println(output);
                        outputBackup=output;
                    }
            }
            catch (NullPointerException e)
            {
                maxOrMin=store[c][col+3];
                outputBackup=output;
                System.out.println(output);
            }
                    
            maxOrMin="";
        }
        
        System.out.println("This is current minimum window: " + minimumWindow);
        System.out.println("This is current maximum window: " + maximumWindow);
          
        for (int c=0; c<row; c++)
        {
            firstIndexLocationStringS = Integer.valueOf(store[c][col]);
            lastIndexLocationStringS = Integer.valueOf(store[c][col+1]);
            
            if((lastIndexLocationStringS-firstIndexLocationStringS+1)>=maximumWindow)
            {
                maximumWindow= (lastIndexLocationStringS-(firstIndexLocationStringS)+1);
            }
            
            if((lastIndexLocationStringS-firstIndexLocationStringS+1)<=minimumWindow)
            {
                minimumWindow= (lastIndexLocationStringS-(firstIndexLocationStringS)+1);
            }
        }
        
        System.out.println("This is final minimum window: " + minimumWindow);
        System.out.println("This is final maximum window: " + maximumWindow);
        
        System.out.println("\n\n-----------------MINIMUM AND MAXIMUM STRING P IN STRING S");
                
        for (int c=0; c<row; c++)
        {
            firstIndexLocationStringS = Integer.valueOf(store[c][col]);
            lastIndexLocationStringS = Integer.valueOf(store[c][col+1]);
            
            if ((lastIndexLocationStringS-firstIndexLocationStringS+1==maximumWindow
                && (store[c][col+3])=="MAXIMUM"))
            {
                outputMaximum = s.substring(firstIndexLocationStringS,(lastIndexLocationStringS+1))
                + " index(" +String.valueOf(firstIndexLocationStringS)+"-"+String.valueOf(lastIndexLocationStringS) +") is a substring containing characters matching permutation: " + store[c][col+2] + "(" +store[c][col+3] 
                +"  Window size: " + String.valueOf(lastIndexLocationStringS-firstIndexLocationStringS+1)+")";
                        
                try
                {
                    if (!outputMaximumBackup.equals(outputMaximum))
                    {
                        System.out.println(outputMaximum);
                        outputMaximumBackup=outputMaximum;
                    }
                }
                catch (NullPointerException e)
                {
                    outputMaximumBackup=outputMaximum;
                    System.out.println(outputMaximum);
                }
            }
            
            if ((lastIndexLocationStringS-firstIndexLocationStringS+1==minimumWindow)
            && (store[c][col+3]=="MINIMUM"))  
            {
                outputMinimum = s.substring(firstIndexLocationStringS,(lastIndexLocationStringS+1)) + " index(" +String.valueOf(firstIndexLocationStringS)+"-"+String.valueOf(lastIndexLocationStringS)+") is a substring containing characters matching permutation: " + store[c][col+2] + "(" +store[c][col+3] +"  Window size: " + String.valueOf(lastIndexLocationStringS-firstIndexLocationStringS+1)+")";
                
                try
                {
                    if (!outputMinimumBackup.equals(outputMinimum))
                    {
                        System.out.println(outputMinimum);
                        outputMinimumBackup=outputMinimum;
                    }
                }
                catch (NullPointerException e)
                {
                    outputMinimumBackup=outputMinimum;
                    System.out.println(outputMinimum);
                }
            }
        }
    }  
}
    
class Permutation
{
    static BigInteger result = new BigInteger("0");
    static BigInteger finalResult = new BigInteger("0");
    static int n;
    static int r;
    static int originalNumber;
    static Map <Integer, BigInteger> factorialResults = new HashMap<Integer, BigInteger>();
    
    static BigInteger runningResult;
    
    static StringJoiner multipleRepeatRVals=new StringJoiner("");
    static boolean hasRepeatRValuesInSample=false;
    
    static BigInteger numberRermutationsWithRepetions;
    
    
    public boolean hasRepeatRvalues()
    {
        return hasRepeatRValuesInSample;
    }
    
    public void getPermutationsWithRepetitionsCalculator(BigInteger permutations, String p)
    {
        System.out.println("\n***PERMUTATIONS*** nPr (without replacement)  WITH REPETITION:\t\t" + "String p: " + p);
        System.out.println("P(n,r) = n! / (n−r)!  /  " + multipleRepeatRVals.toString().substring(0,multipleRepeatRVals.length()-2) + "\t\t(MULTIPLICATION of factorial of occurrences of each UNIQUE r value in n)");
        System.out.println("P(" + originalNumber+","+r+") = " + originalNumber+"!" + " / " + "("+originalNumber+"-"+r+")!" + " / " + runningResult);

        numberRermutationsWithRepetions = permutations.divide(runningResult);
    }
    
    public BigInteger getFinalPermutationsRepetitions()
    {
        return numberRermutationsWithRepetions;
    }
    
    public BigInteger getPermutations(String p)
    {
        System.out.println("***PERMUTATIONS*** nPr (without replacement)\t\t" + "String p: " + p);
        System.out.println("P(n,r) = n! / (n−r)!");
        System.out.println("P(" + originalNumber+","+r+") = " + originalNumber+"!" + " / " + "("+originalNumber+"-"+r+")!");
        
        return result;
    }
    
    public static void getPermutationsWithRepetitions(String strP, Map <Character, Integer> mp)
    {
        char key=' ';
        int val=0;
        int key1;
        
        //long val1;
        BigInteger val1;
        
        long result=0;
        
        for (Character ch: strP.toCharArray())
        {
            if (mp.containsKey(ch))
            {
                int value = mp.get(ch);
                mp.put(ch,(value+1));
            }
            else 
            {
                mp.put(ch,1);
            }
        }
        
        for (Map.Entry<Character, Integer> entry : mp.entrySet()) 
        {
            key = entry.getKey();
            val = entry.getValue();
            
            calculatePermutationsWithRepetitions(key,val);
        }
        
        System.out.println("\n****FACTORIAL INFO:*********");
        for (Map.Entry<Integer, BigInteger> entry : factorialResults.entrySet()) 
        {
            key1 = entry.getKey();
            val1 = entry.getValue();
            
            System.out.println("key: " + key1 + " value: " + val1);
        }
    }
    
    public static BigInteger calculatePermutationsWithRepetitions(char key, int val)
    {
        if (val>1)
        {
            hasRepeatRValuesInSample=true;
            System.out.println("checking the factorial results to ascertain if: " + val + " is present");
            
        if (factorialResults.containsKey(val))
        {
            System.out.println("----------------------------------------------------------------");
            
            result = new BigInteger(String.valueOf(factorialResults.get(val)));
            
            System.out.println("It will perform: " + val+"!" + "=" + result +  "\t due to " +  val + "\toccurrences of: " + key);
            
            try
            {
                
                runningResult = result.multiply(runningResult);
                multipleRepeatRVals.add(val+"!" + " x ");
            }
            catch(NullPointerException e)
            {
                System.out.println("CATCH!!!!!!!!!!!!!!: " + result);
                
                runningResult=new BigInteger(String.valueOf(1));
                
                runningResult = result.multiply(runningResult);
            
                multipleRepeatRVals.add(val+"!" + " x ");
            }
        }
        System.out.println(val+"!  =  " + result);
        
        System.out.println("This is: " + multipleRepeatRVals);
        System.out.println("RUNNING TOTAL (REPETITIONS): " + runningResult + "\t\t" + multipleRepeatRVals.toString().substring(0,(multipleRepeatRVals.length()-2)));
        }
        
        return result;
    }
    
    public static BigInteger Permutations (int n, int r, int originalNumber, Map <Integer, BigInteger> factorialResults)
     {
        Permutation.n=n;
        Permutation.r=r;
	    Permutation.originalNumber=originalNumber;
	    Permutation.factorialResults=factorialResults;
       
        BigInteger temp;
        
        int denominator;
        
        if (originalNumber<r || r<0)
        {
            System.out.println("please enter n ≥ r ≥ 0");
            System.exit(0);
            
            return new BigInteger("0");
        }
        if (n>=1)
        {
            BigInteger setN = new BigInteger(String.valueOf(n));
            BigInteger permFunction = new BigInteger(String.valueOf(Permutations((n-1), r,originalNumber, factorialResults)));
            
            result = new BigInteger(String.valueOf(setN.multiply(permFunction)));
            
            factorialResults.put(n,result);
            
            if (n==originalNumber)
            {
                denominator = originalNumber-r;
                
                if (factorialResults.containsKey(denominator))
                {
                    BigInteger getResult = new BigInteger (String.valueOf(factorialResults.get(denominator)));
                    
                    finalResult=result.divide(getResult);
                    result=finalResult;
                    return result;
                }
            }
            return result;
        }
        
        return new BigInteger("1");
    }
}