Custom Comparators

Generally in sorting, we may have to deal with custom sort functions, so what is the intutution behind those and how a custom compartor can actually work, we will see the stl solution and then hook the compartor in merge sort (our own version of merge sort, working merge sort, which doesn’t give a TLE :D)

Generally, as you must know the sorting is just odering based a rule, ie. whether a number should come before a number or after a number.

std::sort by default uses std::less, which is a < b kind of ordering, which means the smaller number would come first and bigger number goes after this.

https://leetcode.com/problems/custom-sort-string/description/

Intuition

the simplest approach is to define the ordering of characters and then sort the string based on that order. This can be done using both the STL sort function with a comparator

Code

class Solution {
public:

    string customSortString(string order, string s) {
        vector<int> orderMap(26, 0);
        for (int i = 0; i < order.size(); i++) {
            orderMap[order[i] - 'a'] = i;
        }
        // c - 0, b - 1, a - 2
        auto comp = [&](char & c1, char & c2) {
            return orderMap[c1 - 'a'] < orderMap[c2 - 'a'];
        };

        sort(s.begin(), s.end(), comp);
        return s;
    }
};

Working under the hood

To better understand how custom ordering is applied, consider a basic merge sort implementation ( This is not optimized version of merge sort, it is just to understand how things are working under the hood):

void merge(string &s, int start , int mid, int end) {
    // [start ... mid]      -- first half
    // [mid+1 ... end]      -- second half

    string l, r;
    for (int i = start ; i <= mid; i++) l.push_back(s[i]);
    for (int i = mid+1; i <= end; i++) r.push_back(s[i]);

    int p1 = 0, p2 = 0, index = start;

    while (p1 < l.size() && p2 < r.size()) {

        // Default merge rule:
        // If l[p1] < r[p2], l[p1] goes first.
        if (l[p1] < r[p2]) { 
            s[index++] = l[p1++];
        } else {
            s[index++] = r[p2++];
        }
    }

    while (p1 < l.size()) s[index++] = l[p1++];
    while (p2 < r.size()) s[index++] = r[p2++];
}

By default, merge sort places characters based on the normal ASCII ordering:

if (l[p1] < r[p2])

But, we want to do is based on the order, simplest way to change the above line with

if (orderMap[l[p1] - 'a'] < orderMap[r[p2] - 'a'])

To use cpp style, we can pass custom comparator / std::function or template as well.

Using Custom comp in merge sort

class Solution {
public:
    vector<int> orderMap;

    template <typename Comp>
    void merge(string &s, int start , int mid, int end, Comp comp) {

        string l, r;
        for (int i = start ; i <= mid; i++) l.push_back(s[i]);
        for (int i = mid+1; i <= end; i++) r.push_back(s[i]);

        int p1 = 0, p2 = 0, index = start;

        while (p1 < l.size() && p2 < r.size()) {

            // Using custom comparator
            if (comp(l[p1], r[p2])) {
                s[index++] = l[p1++];
            } else {
                s[index++] = r[p2++];
            }
        }

        while (p1 < l.size()) s[index++] = l[p1++];
        while (p2 < r.size()) s[index++] = r[p2++];
    }

    template <typename Comp>
    void mergeSort(string &s, int start, int end, Comp comp) {
        if (start < end) {
            int mid = start + (end - start) / 2;
            mergeSort(s, start, mid, comp);
            mergeSort(s, mid+1, end, comp);
            merge(s, start, mid, end, comp);
        }
    }

    string mergeSort(string order, string s) {
        int start = 0, end = s.size() - 1;

        orderMap.resize(26, 0);
        for (int i = 0; i < order.size(); i++) {
            orderMap[order[i] - 'a'] = i;
        }

        auto comp = [&](char c1, char c2) {
            return orderMap[c1 - 'a'] < orderMap[c2 - 'a'];
        };

        mergeSort(s, start, end, comp);
        return s;
    }

    string customSortString(string order, string s) {
        return mergeSort(order, s);
    }
};