Code Destine

Problem Statement

You have given two strings CustomSorted and Test, both strings contain only lowercase characters. CustomSorted string is sorted in some custom order and does not contain any duplicates.

Sort the input string Test in the same order as CustomSorted string is sorted. For example, if X occurs before Y in CustomSorted string, then X should occur before Y in the returned string.

Example 

Input :- CustomSorted = "cba", Test = "abcd"
Output :- cbad

Input :- CustomSorted = "egabc", Test = "aadepgdbcd"
Output :- egaabcddpd

Solution

This problem can be solved in following steps :-

1. Create an array of characters from the custom sorted string.
2. Create an integer array (count array) of size 26 (Total number of characters in the English language), This array will be used to store the index of each character in the custom sorted string.
3. Traverse the character array from start (index 0) to end (n-1, where n is the length of an array) and convert each character into an index of count array by subtracting the character from ‘a’ and converting it into ASCII code. Assign the current index of character array to the calculated index of count array.
4. Create an array of characters from the test string.
5. Use Merge Sort algorithm to sort the given test string. Merge Sort will use the count array for equality calculations.

Program

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		String result = main.customSortString("egabc", "aadepgdbcd");
		System.out.print(result);
	}
	
	/* Solution */
	public String customSortString(String S, String T) {
        
        int[] countArray = new int[26];
        Arrays.fill(countArray, 26);
        char[] chars = S.toCharArray();
        for(int i=0; i<chars.length; i++){
            countArray[chars[i] - 'a'] = i;
        }
        chars = T.toCharArray();
        mergeSort(chars, 0, chars.length-1, countArray);
        return String.valueOf(chars);
    }
    
    public void mergeSort(char[] chars, int start, int end, int[] countArray){        
        if(start < end){
            int mid = start + (end-start)/2;
            mergeSort(chars, start, mid, countArray);
            mergeSort(chars, mid+1, end, countArray);
            merge(chars, start, end, mid, countArray);
        }
    }
    
    public void merge(char[] chars, int start, int end, int mid, int[] countArray){
        
        char[] temp = new char[end - start + 1];
        int first = start, second = mid+1, i = 0;
        
        while(first <= mid && second <= end){
            temp[i++] = countArray[chars[first]-'a'] < countArray[chars[second]-'a'] ? chars[first++] : chars[second++];
        }        
        while(first <= mid){
            temp[i++] = chars[first++];
        }        
        while(second <= end){
            temp[i++] = chars[second++];
        }
        
        i = 0;
        while(start <= end){
            chars[start++] = temp[i++];
        }
    }
}

Result

egaabcddpd

Similar Post

1. Detect Capital in String
2. First Unique Character in a String
3. Reverse Vowels of a String

That’s all for Custom Order Sorting of String in Java, If you liked it, please share your thoughts in a comments section and share it with others too.