algoadvance

Leetcode 791. Custom Sort String

Problem Statement

You are given two strings, order and s. All the characters of order are unique, and order is a permutation of the characters in s. Reorder the characters of s so that they match the order that order was sorted. More specifically, if a character x appears before a character y in order, then x should appear before y in the reordered string.

Return any permutation of s that respects this ordering.

Example 1:

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

Constraints:

Clarifying Questions

  1. Is it guaranteed that all characters in s will appear in order?
    • Yes, since order is a permutation of the characters in s.
  2. Should we consider the frequency of characters in s while sorting?
    • Yes, we need to maintain the frequency of characters.
  3. Can there be any additional characters in s which are not in order?
    • No, as per the problem statement order is a permutation of the characters in s.

Strategy

  1. Frequency Count:
    • Count the frequency of each character in s.
  2. Sorting as per Order:
    • Traverse through each character in order and append the characters from s to the result based on their count.
  3. Appending Remaining Characters:
    • After sorting according to the order, append any remaining characters that are not included in the order. But as per problem statement, this step won’t be necessary since order is a permutation of characters present in s.

Code

import java.util.HashMap;

public class CustomSortString {
    
    public String customSortString(String order, String s) {
        // Map to count frequency of characters in s
        HashMap<Character, Integer> countMap = new HashMap<>();
        
        for (char ch : s.toCharArray()) {
            countMap.put(ch, countMap.getOrDefault(ch, 0) + 1);
        }
        
        StringBuilder result = new StringBuilder();
        
        // Append characters as per the order
        for (char ch : order.toCharArray()) {
            if (countMap.containsKey(ch)) {
                int count = countMap.get(ch);
                for (int i = 0; i < count; i++) {
                    result.append(ch);
                }
                // Remove the character from the map once it is processed
                countMap.remove(ch);
            }
        }
        
        // Append remaining characters if any
        // which should not exist per problem statement
        for (char ch : countMap.keySet()) {
            int count = countMap.get(ch);
            for (int i = 0; i < count; i++) {
                result.append(ch);
            }
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        CustomSortString sorter = new CustomSortString();
        String order = "cba";
        String s = "abcd";
        System.out.println(sorter.customSortString(order, s)); // Output: "cbad"
    }
}

Time Complexity

The overall time complexity is O(n + m). Space complexity is O(n) for storing the frequency count.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI