algoadvance

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 returned string.

Return any permutation of s that satisfies this property.

Example:

Input:
order = "cba"
s = "abcd"
Output:
"cbad"

Explanation:
"a", "b", "c" were sorted in the original order. So "cba" should appear in the returned string. As "d" doesn't exist in order, it can be at any position in the returned string.

Clarifying Questions

  1. Is the input always valid?
    • Yes, you can assume the input strings order and s are non-empty and order contains only unique characters.
  2. How should characters in s that do not appear in order be handled?
    • Characters not in order can appear in any position relative to the characters specified in order, as they have no specified order.
  3. Can order contain characters not present in s?
    • Yes, order may contain characters that do not appear in s.
  4. What should be done in case of an empty order string?
    • This situation won’t occur because per the assumption, the input strings order and s are non-empty.

Strategy

  1. Create a frequency Counter for characters in s. This will help to keep track of the number of occurrences of each character.
  2. Build the result string using the order string. For each character in order, append it to the result as many times as it appears in s using the Counter created in step 1.
  3. Append remaining characters that were not in order. After processing all characters in order, append any characters in s that do not appear in order.

Code

from collections import Counter

def customSortString(order: str, s: str) -> str:
    # Step 1: Create a frequency counter for characters in s
    count = Counter(s)
    
    # Step 2: Build the result string using the `order` string
    result = []
    for char in order:
        if char in count:
            result.append(char * count[char])
            del count[char]  # remove the character completely
    
    # Step 3: Append remaining characters that were not in `order`
    for char, freq in count.items():
        result.append(char * freq)
    
    # Join the result list to form the final string
    return ''.join(result)

# Example usage
order = "cba"
s = "abcd"
print(customSortString(order, s))  # Output: "cbad"

Time Complexity

  1. Counting frequencies: Constructing the frequency counter for s takes O(n), where n is the length of s.
  2. Building the result string: Iterating through the order string and constructing the result substring for each character present in order takes O(m * freq) where m is the length of order and freq is the average frequency of characters in s. Since freq can be considered as a constant, this step effectively takes O(m).
  3. Appending remaining characters: Iterating through characters not in order and appending them to the result string takes O(n - m), where n - m is the count of characters not in order.

Therefore, the overall time complexity of the solution is O(n + m) where n is the length of s and m is the length of order.

Try our interview co-pilot at AlgoAdvance.com