Custom Sort String Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Facebook GoogleViews 3201

Problem Statement

The Custom Sort String LeetCode Solution – “Custom Sort String” states that you’re given two strings order and s. All characters of string order are unique and they are sorted in the custom order. We need to permute the characters of s and such that the characters follow the same order as present in the string order.

More formally, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Example:

Custom Sort String Leetcode Solution

 

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

Explanation:

  • The order of characters defined by the string order is:-  c < b < a.
  • For the string s, we need to permute its characters such that they follow the same order defined by the string order.
  • Hence, valid permutation is: “cbad”.
  • Note that if any character is absent in the above order defined, that character should be placed at the last position of the permutation.
Input:  order = "cbafg", s = "abcd"
Output: "cbad"

 

Explanation:

  • The order of characters defined by the string order is:-  c < b < a < f < g .
  • Hence, we need to permute characters of string s on the basis of the above order.
  • Valid Permutation is: “cbad”.

Approach

Idea:

  1. The main idea to solve this problem efficiently is to use a frequency table (Hashing).
  2. Store all the unique characters frequencies of the string s in the frequency table.
  3. Now, since we need to permute the characters of string s on the basis of order defined by string order, we’ll iterate in the string order and for each character, we’ll append exactly x occurrences of the same character to our answer (x = frequency of current character in string s).
  4. For the character which is present in string s but absent in string order, they’ll be placed at the last position of our answer string.

Code

C++ Custom Sort String Leetcode Solution:

class Solution {
public:
    string customSortString(string order, string s) {
        vector<int> freq(26);
        for(auto& c:s){
            freq[c-'a']++;
        }
        string ans;
        for(auto& c:order){
            while(freq[c-'a']-- > 0){
                ans.push_back(c);
            }
        }
        for(char c='a';c<='z';c++){
            while(freq[c-'a']-- > 0){
                ans.push_back(c);
            }
        }
        return ans;
    }
};

Java Custom Sort String Leetcode Solution:

class Solution {
    public String customSortString(String order, String s) {
        int[] freq = new int[26];
        for(char c:s.toCharArray()){
            freq[c-'a']++;
        }
        StringBuilder ans = new StringBuilder();
        for(char c:order.toCharArray()){
            while(freq[c-'a']-- > 0){
                ans.append(c);
            }
        }
        for(char c='a';c<='z';c++){
            while(freq[c-'a']-- > 0){
                ans.append(c);
            }
        }
        return ans.toString();
    }
}

Complexity Analysis for Custom Sort String Leetcode Solution

Time Complexity

The time complexity of the above code is O(N+M) where N = length of string order and M = length of string s. We’re iterating in the string s as well as string order exactly one time.

Space Complexity

The space complexity of the above code is O(N), which is the same size as of string order.

Reference: https://computersciencewiki.org/index.php/Hashing

Translate »