Smallest KMP

Smallest KMP 

Chef has a string S$S$. He also has another string P$P$, called pattern. He wants to find the pattern in S$S$, but that might be impossible. Therefore, he is willing to reorder the characters of S$S$ in such a way that P$P$ occurs in the resulting string (an anagram of S$S$) as a substring.

Since this problem was too hard for Chef, he decided to ask you, his genius friend, for help. Can you find the lexicographically smallest anagram of S$S$ that contains P$P$ as substring?

Note: A string B$B$ is a substring of a string A$A$ if B$B$ can be obtained from A$A$ by deleting several (possibly none or all) characters from the beginning and several (possibly none or all) characters from the end.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single string S$S$.
• The second line contains a single string P$P$.

Output

For each test case, print a single line containing one string ― the smallest anagram of S$S$ that contains P$P$.

Constraints

• 1≤T≤10$1\le T\le 10$
• 1≤|P|≤|S|≤105$1\le |P|\le |S|\le {10}^5$
• S$S$ and P$P$ contain only lowercase English letters
• there is at least one anagram of S$S$ that contains P$P$

Subtasks

Subtask #1 (20 points): |S|≤1,000$|S|\le 1,000$

Subtask #2 (80 points): |S|≤105$|S|\le {10}^5$

Example Input

3
akramkeeanany
aka
supahotboy
bohoty
daehabshatorawy
badawy

Example Output

aaakaeekmnnry
abohotypsu
aabadawyehhorst

Solution Java 8:

import java.util.Arrays;

import java.util.Scanner;

class Solution {

public static String StrSort(String str,String p) {

  char[] sortstr = str.toCharArray();

  Arrays.sort(sortstr);

  String s = new String(sortstr);

  String begin,end,con = null;

  for(int i=0; i<sortstr.length; i++)

   if((sortstr[i]<=p.charAt(0)) && (sortstr[i+1]>p.charAt(0))             {

             begin = s.substring(0,i+1);

             end = s.substring(i+1);

             con = begin + p + end;

             break;

    }

          return con;

}

public static void main(String[] args) {

 Scanner sc = new Scanner(System.in);

 int test = sc.nextInt();

 sc.nextLine();

 String s = "",p="";

 for (int i = 0; i < test; i++) {

     s = sc.nextLine();

     p = sc.nextLine();

     for (int j = 0; j < p.length(); j++) {

for (int k = 0; k < s.length(); k++) {

   if (p.charAt(j) == s.charAt(k)) {

s = s.substring(0, k) + s.substring(k + 1);

break;

    }

}

      }

      System.out.println(StrSort(s,p));

 }

sc.close();

      }

}