/*
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.
               
//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 long 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>();
        
        //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 = "aabcdefghij";
        //String s = "abcdefghijkabcdefghij";
        
        //String s  = "abcdabead";
        //String p="abd";
        
        
        //String s  = "amcdaibaxf";
        //String p="abdho";
        
        String s  = "abcdabead";
        String p="abd";
        
        
        int originalNumber=p.length();
        
        int n;
        int r = p.length();
        
        //we know minimum window can not be greater than length of String s
        minimumWindow=s.length();
        
        maximumWindow=0;
        
        //Map <Integer, Long> m = new HashMap<>();
        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;
        
        
        //int difference = 0;
        BigInteger difference= new BigInteger("0");
        
        List <String> backupValuesSet = new ArrayList<>();
        int currentSetSize;
        BigInteger newSetSize;
        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)
                {
                    //System.out.println("random num: " + temp1);
                    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 = st.size();
            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("1000000")).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);
                
                //we need to set back to default value since it is executing next template word
                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);
				                    
				                    //the only technique is to break out of both do while loops
				                    //so that it picks next template word from valuesSet
				                    //System.out.println("StringBuilder being emptied: " + sb.toString());
                                    //sb.delete(0,sb.length());
                                    //i=s.length();
                                    
                                    //we also have to prevent it from populating the sb otherwise it will still continue executing the
                                    //inner do while loop 
                                    //break;
                                    
                                    //this breaks inner do while loop
                                    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)+")");
				
				//This is now incorrect. We want to examine everything from startPos onwards
				//System.out.println("SUBSTRING EXAMINED: " + s.substring(startPos,(startPos+p.length())));
				
				//for unknown reason, if the end argument is not passed in, it only retreives three characters from the substring
				//System.out.println("SUBSTRING EXAMINED: " + s.substring(strartPos);
				
				//So I required following remediation
				System.out.println("SUBSTRING EXAMINED: " + s.substring(startPos,s.length()));
				                
				                
				                //This actually difficult to perform and save execution cycles
				                //It will make my code extremely difficult by implementing logic
				                //I would need to literally take the logic up the point where it will generate a new template word
				                //So it would need to break out of both do while loops, which would be massive overhead to the readability
				                
				                //This logic is describing scenario as such:
				                //if examining the following string s = "cbead"   string p (permutation template word) = "cdg"
				                //We know it does not exist....
				                //So basically we would not want it to perform operation starting at index =1   or index =2
				                
				                    
				                
                                
				                
				                
				            //this if has same condition as outer if
				            //since the status could potentially change if there are insufficient characters
				            
				              if (hasSufficientCharactersStringS)
				              {
                                
				                
                                //This level of checking is still fine
                                if (Character.toString(s.charAt(i)).indexOf(sb.toString().charAt(pos))==0)
                                {
                                    System.out.println("char found: " + sb.toString().charAt(pos) + 
                                    "    at index: " + i);
                                    
                                    
                                    //in this circumstance, since we are now flexible with all characters of String p appearing in String s 
                                    //across any length of String s, we need to keep a track of the index every time that it finds a match
                                    //if this index location is overwritten, this will be used to present to end user the actual substring of String s
                                    //that contained all letters of String p. This is taken to be variable i;
                                    
                                    lastIndexLocationStringS=i;
                                    //System.out.println("last index location: "  + lastIndexLocationStringS);
                                    
                                    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;
                                    
                                    //this will ensure we capture the first index of character match
                                    if (sb.length()==p.length()-1)
                                    {
                                        firstIndexLocationStringS=i;
                                    }
                                    
                                    
                                    
                                }
                            }
                                
                                
                                //this runs right to inner do while loop
				                if (hasSufficientCharactersStringS)
				                {
                                
                                //at this point we empty entire stringbuilder since we reached end of String s
                                //and all characters from String p not matched
                                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;
                                    
                                    //we need to record another boolean to indicate that StringBuilder was cleared since it reached last character
                                    //String s
                                    
                                    hasIncompleteLettersInStringS=true;
                                    break;
                                }
                                
                                //I no longer required this since we need to execute through remainder of String s
                                /*
                                else
                                {
                                    //System.out.println("NO MATCH FOUND");
                                    //System.out.println("StringBuilder being emptied: " + sb.toString());
                                    sb.delete(0,sb.length());
                                    hasCharFound=false;
                                    break;
                                }
                                */
                                
                            }
                        }
                        }
                        
                    }
                        
                        
                    }while(!sb.toString().isEmpty());
        
                    if (sb.toString().isEmpty() && hasCharFound && !hasIncompleteLettersInStringS && hasSufficientCharactersStringS)
                    {
                        //We need to simply have lastIndexLocationStringS as the substring since this is last position
                        //where it has found a character from String p
                        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("**********************************************************");
                        
                        //Now it is all much simple. I had caused extreme difficulty previously in which I tried
                        //over analyse the question....
                        //At the point in time, I now have the start index and end index (String s) containing all the characters for String p
                        //I also will have it for all permutations possible of String p.
                        
                      
                        
                        System.out.println("String p (all characters) found within window ("+ (lastIndexLocationStringS-(firstIndexLocationStringS)+1) + ")"    
                        +  ": \tString s (index: " + firstIndexLocationStringS+" - " + lastIndexLocationStringS+")");
                        
                        //The && part in the if statement provides extra validation but not strictly required
                        
                        
                        if(lastIndexLocationStringS-startPos>=p.length())
                        {
                        
                        //if((lastIndexLocationStringS-firstIndexLocationStringS+1)<=minimumWindow)
                        //{
                            
                            
                            System.out.println("----STORING WINDOW RESULT (MINIMUM): " +s.substring(startPos,(lastIndexLocationStringS+1)) 
                            + " (Index: " + firstIndexLocationStringS + "-" + lastIndexLocationStringS + "  Window: " + (lastIndexLocationStringS-firstIndexLocationStringS+1)+")" + "  String p: " + valuesSet[entry]);
                            
                            //need to store the startPos, lastIndexLocationStringS and also String p
                        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++;
                        //col=0;
                        //System.out.println("ROW NUMBER: " + row);
                        //}
                        
                        //if((lastIndexLocationStringS-firstIndexLocationStringS+1)>=maximumWindow)
                        //{
                            //maximumWindow= (lastIndexLocationStringS-(firstIndexLocationStringS)+1);
                            
                            System.out.println("----STORING WINDOW RESULT (MAXIMUM): " +s.substring(startPos,(lastIndexLocationStringS+1)) 
                            + " (Index: " + firstIndexLocationStringS + "-" + lastIndexLocationStringS + "  Window: " + (lastIndexLocationStringS-firstIndexLocationStringS+1)+")" + "  String p: " + valuesSet[entry]);
                            
                            //need to store the startPos, lastIndexLocationStringS and also String p
                        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++;
                        //col=0;
                        //System.out.println("ROW NUMBER: " + row);
                        //}
                        
                        }
                    }
		            if (sb.toString().isEmpty() && !hasCharFound && hasIncompleteLettersInStringS)
                    {
                        //We know the delimiter here will simply be the last position on String s.
                        //since we have reached the end and also has 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++;
                
                //we are still bound by this condition since we do not want to perform check on String s
                //in which StringBuilder (String p) is still populated AND insufficient characters left in String s
                //The inner do while loop keeps running until StringBuilder sb is not empty
                //so we know when it reaches here, sb is empty (ie it is ready to start execution again)
                
                //I have added another condition in while loop to break out
                }while(p.length()+startPos<s.length()  && hasSufficientCharactersStringS);

                counter=0;
                startPos=0;
            }
        }
        
         //required to obtain minimum lastIndexLocationStringS - startPos
        //output this information
        
        //col=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]);
            
            //if (lastIndexLocationStringS-startPos==minimumWindow)
            //{
            
                    //minimumWindow= (lastIndexLocationStringS-(firstIndexLocationStringS)+1);
            
                    //if (store[c][col+3]=="MINIMUM" && (lastIndexLocationStringS-firstIndexLocationStringS+1)==minimumWindow)
                    //{
                    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="";
                    
                    
                    
                    //}
                    
                    /*
                    if (store[c][col+3]=="MAXIMUM")
                    {
                     System.out.println((s.substring(firstIndexLocationStringS,(lastIndexLocationStringS+1))) 
                     + " index(" +firstIndexLocationStringS+"-"+lastIndexLocationStringS+") is a substring containing characters matching permutation: " 
                     + store[c][col+2] + "(" +store[c][col+3] +"  Window size: " + maximumWindow+")");    
                    }
                */
            //}
            //col=0;
        }
        
        System.out.println("This is current minimum window: " + minimumWindow);
          System.out.println("This is current maximum window: " + maximumWindow);
          
                //NOW THIS WILL GET ALL OF THE
        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"))
            {
            
            //outputMaximumBackup=outputMaximum;
                
                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)+")";
                //System.out.println("NOT OUTPUT: " + output);    
                
                //System.out.println("backup: " + outputMaximumBackup);
                //System.out.println("new: " + outputMaximum);
                
                    //if (outputMaximumBackup!=null)
                    //{
                    try
                    {
                    if (!outputMaximumBackup.equals(outputMaximum))
                    {
                        System.out.println(outputMaximum);
                        outputMaximumBackup=outputMaximum;
                    }
                    }
                    catch (NullPointerException e)
                    {
                        outputMaximumBackup=outputMaximum;
                        System.out.println(outputMaximum);
                    }
                    //}
                //}
            }
            
            
            
            
            
            
            
        
           
            //System.out.println()
            
            //System.out.println("VAL: " + col);
            
            if ((lastIndexLocationStringS-firstIndexLocationStringS+1==minimumWindow)
            && (store[c][col+3]=="MINIMUM"))  
            
            {
                //outputMinimumBackup=outputMinimum;
                
                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)+")";
                //System.out.println("NOT OUTPUT: " + output);    
                
                //System.out.println("backup: " + outputMinimumBackup);
                //System.out.println("new: " + outputMinimum);
                
                    
                    //output = new StringJoiner(segment);
                     //+ " 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) +")");
                    
                    //System.out.println("THIS IS OUTPUT: " + segment);
                
                //if no contents in the backup, this would be first execution    
                //if (outputBackup==null)
            //    {
              //      System.out.println("ONLY ONCE");
                //    outputBackup=output;
                    //System.out.println(output);
                //}
                
                //there is already a value....
                //so not first execution
                //else
                //{
                    try
                    {
                    if (!outputMinimumBackup.equals(outputMinimum))
                    {
                        System.out.println(outputMinimum);
                        outputMinimumBackup=outputMinimum;
                    }
                    }
                    catch (NullPointerException e)
                    {
                        outputMinimumBackup=outputMinimum;
                        System.out.println(outputMinimum);
                    }
                //}
            }
            
        }
        
        
        
        //difference = newSetSize;
    }  
}
    
class Permutation
{
    //static long result=0;
    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 long runningResult=0;
    static BigInteger runningResult;
    
    static StringJoiner multipleRepeatRVals=new StringJoiner("");
    static boolean hasRepeatRValuesInSample=false;
    
    //static long numberRermutationsWithRepetions;
    static BigInteger numberRermutationsWithRepetions;
    
    
    public boolean hasRepeatRvalues()
    {
        return hasRepeatRValuesInSample;
    }
    
    //public void getPermutationsWithRepetitionsCalculator(long permutations, String p)
    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/runningResult;
        numberRermutationsWithRepetions = permutations.divide(runningResult);
    }
    
    //public long getFinalPermutationsRepetitions()
    public BigInteger getFinalPermutationsRepetitions()
    {
        return numberRermutationsWithRepetions;
    }
    
    //public long getPermutations
    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 long calculatePermutationsWithRepetitions(char key, int val)
    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 = factorialResults.get(val);
            result = new BigInteger(String.valueOf(factorialResults.get(val)));
            
            System.out.println("It will perform: " + val+"!" + "=" + result +  "\t due to " +  val + "\toccurrences of: " + key);
            
            //THIS WAS MAJOR CHANGE IN THE CODE
            //I HAD TO EXECUTE THIS TO REMEDIATE NullPointerException
            //if (runningResult==0)
            //if (runningResult.equals(null))
            try
            {
                runningResult=result;
                multipleRepeatRVals.add(val+"!" + " x ");
            }
            catch(NullPointerException e)
            {
                //runningResult = result * runningResult;
                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)
    //public static BigInteger Permutations (BigInteger n, BigInteger r, BigInteger originalNumber, Map <Integer, Long> factorialResults)
     {
        Permutation.n=n;
        Permutation.r=r;
	    Permutation.originalNumber=originalNumber;
	    Permutation.factorialResults=factorialResults;
       
        //int temp;
        BigInteger temp;
        
        int denominator;
        
        if (originalNumber<r || r<0)
        {
            System.out.println("please enter n ≥ r ≥ 0");
            System.exit(0);
            
            //return 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 = (n* (Permutations (n-1, r,originalNumber, factorialResults)));
            result = new BigInteger(String.valueOf(setN.multiply(permFunction)));
            //System.out.println(result);
            
            factorialResults.put(n,result);
            
            if (n==originalNumber)
            {
                denominator = originalNumber-r;
                //denominator=new BigInteger(String.valueOf(originalNumber-r));
                
                if (factorialResults.containsKey(denominator))
                {
                    //return result / (long)factorialResults.get(denominator);
                    BigInteger getResult = new BigInteger (String.valueOf(factorialResults.get(denominator)));
                    
                    System.out.println("result: " + result);
                    System.out.println("getResult: " + getResult);
                    System.out.println("aa: " + result.divide(getResult));
                    
                    //I had to include this late in my code (30/08/2025) since the value in result was being shown without the division when
                    //I tried to retrieve the value when calling method getPermutations from the Main class
                    finalResult=result.divide(getResult);
                    result=finalResult;
                    return result;
                }
            }
            return result;
        }
        
        //return 1;
        return new BigInteger("1");
    }
}