CareerCup

Does the solution need to be made generic? If so, how are the lengths of input strings bound?

If the pre-sorted string is always small in distinct letters relative to the string being sorted, insert is acceptable as other sorting algorithms suffer when most of the string is already 'sorted'.

Insert sort is also preferable for small strings in general. That is why it is one way to better performance of quicksort after a threshold of sub-string/array has been reached.

Observing letters not included in the sorting string do not change position related to one another, one solution is to use a new Character data object implementing comparable interface where f = 0, g = 1, h = 2, a = 3, b = 4, else = 99. Then use merge sort which is a 'stable' sort, preserving positions of 'equal' items relative to one another.

public static void main(String[] args) {
		
		String s1 = "fghab";
		String s2 = "abfmgfghnaixcv";
		String remainder = "";
		String result="";
		int i=0;
		
		Hashtable<Character,Integer> h = new Hashtable<Character,Integer>();
		for(i=0;i<s1.length();i++) {
			h.put(s1.charAt(i), 0 );
		}
		
		for(i=0;i<s2.length();i++) {
			if(h.containsKey(s2.charAt(i))) {
				int count = h.get(s2.charAt(i));
				h.put(s2.charAt(i), count+1);
			}
			else {
				remainder+=s2.charAt(i);
			}
		}
		
		for(i=0;i<s1.length();i++) {
			int count = h.get(s1.charAt(i));
			for(int j=0;j<count;j++) {
				result+=s1.charAt(i);
			}
		}
		
		result+=remainder;
		System.out.println(result);
}

My idea is to count the number of each char of the unsorted string s2. Then scan s1, get the substr consisting of the chars in s2 and s1 in the sorted order of s1, and set the numbers of these chars zero. And then scan s2, if its number is zero, skip otherwise output

#include<stdio.h>
int main()
{
char *string s1="fghab";
char * string s2="abfmgfghnaixcv"
int count[26];
int i;
for(i=0;i<strlen(s2);i++)
count[s2[i]-'a']++;
int j=0;
int temp;
for(i=0;i<strlen(s1);i++){
temp=count[s1[i]-'a'];
if(temp)
while(temp){
s2[j++]=s1[i];
temp--;
}
}
s2[j]='\0';

main()
{
char sam[]={"fghab"};
char obj[]={"abfmgfghnaixcv"};
char t, c;
int strlens = strlen(sam);
int strleno = strlen(obj);
int i,j, k=0;

for(i=0; i<strlens; i++)
{
t = sam[i];
for(j=k; j<strleno; j++)
{
if(obj[j] == t)
{
//exchange obj[j] and obj[k]
obj[j] = obj[k];
obj[k] = t;
k++;
}
}
}

printf("%s\n\r", obj);


}

1) create a lookup table for string of smaller size indicating the order of the character in the string, for other characters just add the order as int_max
in this case lookup table will be

arr[26]
in order = 0;
for each char x in s1
arr[121-(int)x] = order++;

2) perform a merge sort on the second array using the lookup table

Count the number of characters in S2 and place in a hash.
Now scan each alphabet in S1 character by character from left to right.
Take a character and search in hash, if present print the number of characters that are their in S2 for that character.

std::stable_sort(s2.begin(),s2.end(),[&s1](char a, char b)->bool { return s1.find(a) < s1.find(b); });