Custom Sort String

Medium

Apple

15 views

Topics:

Strings

You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously.

Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Return any permutation of s that satisfies this property.

Example 1:

Input: order = "cba", s = "abcd"

Output: "cbad"

Explanation: "a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.

Example 2:

Input: order = "bcafg", s = "abcd"

Output: "bcad"

Explanation: The characters "b", "c", and "a" from order dictate the order for the characters in s. The character "d" in s does not appear in order, so its position is flexible.

Following the order of appearance in order, "b", "c", and "a" from s should be arranged as "b", "c", "a". "d" can be placed at any position since it's not in order. The output "bcad" correctly follows this rule. Other arrangements like "dbca" or "bcda" would also be valid, as long as "b", "c", "a" maintain their order.

Constraints:

1 <= order.length <= 26
1 <= s.length <= 200
order and s consist of lowercase English letters.
All the characters of order are unique.

Custom Sort String

Medium

Apple

15 views

Topics:

Strings

You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously.

Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Return any permutation of s that satisfies this property.

Example 1:

Input: order = "cba", s = "abcd"

Output: "cbad"

Explanation: "a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.

Example 2:

Input: order = "bcafg", s = "abcd"

Output: "bcad"

Explanation: The characters "b", "c", and "a" from order dictate the order for the characters in s. The character "d" in s does not appear in order, so its position is flexible.

Following the order of appearance in order, "b", "c", and "a" from s should be arranged as "b", "c", "a". "d" can be placed at any position since it's not in order. The output "bcad" correctly follows this rule. Other arrangements like "dbca" or "bcda" would also be valid, as long as "b", "c", "a" maintain their order.

Constraints:

1 <= order.length <= 26
1 <= s.length <= 200
order and s consist of lowercase English letters.
All the characters of order are unique.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `order` string contain characters not present in the `string` string?
Can either the `order` string or the `string` string be empty? What should I return in those cases?
Does case matter? Are the characters in `order` and `string` case-sensitive, and should I preserve the original casing?
If a character appears multiple times in the `string` string, should its relative ordering based on `order` be preserved?
Is the `order` string guaranteed to contain only unique characters, or could it have duplicates?

Brute Force Solution

Approach

The brute force method for custom sorting involves trying every possible arrangement of the string you want to sort. It exhaustively explores each permutation based on the custom order, and then determines which one matches the order.

Here's how the algorithm would work step-by-step:

Consider all the possible arrangements of the characters in the string we want to sort.
For each possible arrangement, we check if that arrangement follows the custom order we were given.
If the arrangement follows the custom order, we keep it.
After checking all possible arrangements, we choose the one that follows the custom order. This will be our sorted string.

Code Implementation

def custom_sort_string_brute_force(custom_order, string_to_sort):
    import itertools

    all_possible_arrangements = list(itertools.permutations(string_to_sort))
    
    sorted_arrangements = []

    for possible_arrangement in all_possible_arrangements:
        is_sorted = True
        arrangement_string = ''.join(possible_arrangement)

        #Check if the arrangement follows the custom order
        for i in range(len(arrangement_string) - 1):
            first_char = arrangement_string[i]
            second_char = arrangement_string[i+1]

            first_char_index = -1
            second_char_index = -1

            if first_char in custom_order:
                first_char_index = custom_order.index(first_char)
            else:
                first_char_index = len(custom_order) #Place at end if not in custom order

            if second_char in custom_order:
                second_char_index = custom_order.index(second_char)
            else:
                second_char_index = len(custom_order) #Place at end if not in custom order

            # Determine if arrangement is ordered
            if first_char_index > second_char_index:
                is_sorted = False
                break
        
        # Store sorted arrangements
        if is_sorted:
            sorted_arrangements.append(arrangement_string)

    # Return the first sorted arrangement
    if sorted_arrangements:
        return sorted_arrangements[0]
    else:
        return ""

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force approach first generates all possible permutations of the string, where n is the length of the string to be sorted. Generating all permutations takes O(n!) time. Then, for each of the n! permutations, we need to check if it adheres to the custom order. Checking a single permutation of length n to see if it is correctly ordered takes O(n) time. Therefore, the overall time complexity is O(n! * n).

Space Complexity

O(N!) – The brute force approach, as described, explores all possible permutations of the input string. Generating all permutations of a string of length N requires storing each permutation, leading to a space complexity proportional to the number of permutations, which is N factorial (N!). Therefore, auxiliary space is used to store these permutations. As N increases, the number of permutations grows extremely rapidly, dominating space usage. Thus, the space complexity is O(N!).

Optimal Solution

Approach

The key is to understand the sorting order we must follow. We can efficiently count each character's appearance and then build the new string according to the custom order, handling any leftover characters afterward.

Here's how the algorithm would work step-by-step:

First, count how many times each letter appears in the string we want to sort.
Then, go through the custom order string, and for each letter in the custom order, add that letter to our new string as many times as we counted.
Finally, check if there are any letters in the original string that were not in the custom order. Add them to the end of our new string, based on their counts.

Code Implementation

def custom_sort_string(order_string, string_to_sort):
    character_counts = {}
    for char in string_to_sort:
        character_counts[char] = character_counts.get(char, 0) + 1

    sorted_string = ''

    # Build string based on custom order
    for char in order_string:
        if char in character_counts:
            sorted_string += char * character_counts[char]
            del character_counts[char]

    # Handle leftover characters not in custom order
    # Append remaining characters based on their counts
    for char, count in character_counts.items():
        sorted_string += char * count

    return sorted_string

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n + m) – Let n be the length of the string we want to sort (T) and m be the length of the custom order string (S). Counting the character frequencies in T takes O(n) time. Iterating through the custom order string S and appending characters to the result takes O(m) time, since we perform a constant amount of work for each character in S. Adding any remaining characters from T (that are not in S) to the result also takes at most O(n) time as, in the worst case, we iterate through the frequencies to find remaining characters. Therefore, the overall time complexity is O(n + m), which simplifies to O(n+m).

Space Complexity

O(1) – The algorithm uses a character count array or hash map to store the frequency of characters from the input string. Since we are dealing with characters, the size of this data structure will be at most the number of unique characters in the character set (e.g., 26 for lowercase English letters). No other significant auxiliary space is used, so the space complexity is constant with respect to the input string's length N, meaning the space required does not scale with the input string's size. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
order string is null or empty	Return the input string directly as no custom sorting is needed.
string is null or empty	Return an empty string since there is nothing to sort.
order string contains duplicate characters	The solution should process the first occurrence of each character in the order string and ignore subsequent duplicates.
string contains characters not present in the order string	Append these characters to the end of the sorted string in their original order of appearance in the input string.
order string contains all possible characters and string contains all possible characters	The sorted output will be the characters in the same order as the order string, implying the solution should be able to handle all characters.
string contains duplicate characters	The solution should correctly count and arrange each character based on the order string, maintaining the number of occurrences.
Very long input string	Ensure the solution uses efficient data structures (e.g., hash map) to avoid performance issues such as exceeding time limit.
Order string only contains some characters from the string.	The characters from the input string that are not present in the order string should be appended to the result in their original order.