Custom Sort String - Leetcode Solution

The Custom Sort String problem on LeetCode asks us to sort a string based on a given order of characters. The problem can be solved using several approaches, but the most efficient solution is to use a counting sort algorithm.

The solution strategy is to create a character count array of the given string S. We then iterate over the target string T and insert the characters into the output string based on the character count array. If the character is not present in the count array, it means it is not in the given order and should be appended to the end of the output string.

Here are the detailed steps to solve this problem:

1. Create a character count array with 26 elements initialized to 0. We will use this to keep track of the frequency of each character in the given string S.

2. Iterate over the characters in the string S and increment the count for each character in the character count array.

3. Initialize an empty output string.

4. Iterate over the characters in the target string T.

5. If the character is present in the character count array, append the character to the output string for the number of times equal to its count in the character count array.

6. Set its count to 0 in the character count array.

7. If the character is not present in the character count array, append the character to the end of the output string.

8. Finally, return the output string.

Here is the implementation of the above solution in Python:

def customSortString(S: str, T: str) -> str:
    count = [0] * 26
    for c in S:
        count[ord(c) - ord('a')] += 1

    output = ''
    for c in T:
        if count[ord(c) - ord('a')] > 0:
            output += c * count[ord(c) - ord('a')]
            count[ord(c) - ord('a')] = 0
        else:
            output += c

    for i in range(26):
        if count[i] > 0:
            output += chr(i + ord('a')) * count[i]

    return output

The time complexity of this solution is O(N), where N is the length of the target string T. The space complexity is also constant, as we are using a fixed size character count array.

In conclusion, the Custom Sort String problem on LeetCode can be solved efficiently using a counting sort algorithm. The solution involves creating a character count array, iterating over the target string and inserting the characters into the output string based on the character count array. If the character is not present in the count array, it means it is not in the given order and should be appended to the end of the output string.

1