We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Custom Sort String

Number: 807

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Uber, Bloomberg, Apple

Problem Description

Given two strings, order and s, rearrange the characters in s such that they follow the order defined by the string order. Characters in s that are not present in order can be placed arbitrarily in the resulting string.

Key Insights

  • Use a hash table (or dictionary) to count the occurrences of each character from s.
  • Iterate over the order string to add characters into the result according to the custom order.
  • For any remaining characters in s (i.e., those not in order), append them in any order.

Space and Time Complexity

Time Complexity: O(n + m) where n is the length of s and m is the length of order. Space Complexity: O(n) to store the frequency of characters from s.

Solution

We can solve this problem by first counting the frequency of each character in s using a hash table. Then, iterate through each character in the order string - for each character found, append it to the result as many times as it appears (and remove or update its count). Finally, process the remaining characters from s (those not present in order) and append them at the end of the result. This simple approach efficiently meets the problem requirements.

Code Solutions

# Count the frequency of each character in s using a dictionary
def customSortString(order, s):
    char_frequency = {}
    for char in s:
        if char in char_frequency:
            char_frequency[char] += 1
        else:
            char_frequency[char] = 1

    # Build the result by processing characters in the 'order' string
    result = []
    for char in order:
        if char in char_frequency:
            result.append(char * char_frequency[char])  # Append char repeated frequency times
            del char_frequency[char]  # Remove the char from the dictionary as it is processed

    # Append remaining characters that were not in 'order'
    for char, count in char_frequency.items():
        result.append(char * count)

    # Join list into a final string result
    return "".join(result)

# Example usage:
print(customSortString("cba", "abcd"))  # Expected output: "cbad" or any valid permutation
← Back to All Questions