Problem description:

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :
Input:
S = “cba”
T = “abcd”
Output: “cbad”
Explanation:
“a”, “b”, “c” appear in S, so the order of “a”, “b”, “c” should be “c”, “b”, and “a”.
Since “d” does not appear in S, it can be at any position in T. “dcba”, “cdba”, “cbda” are also valid outputs.

Note:

S has length at most 26, and no character is repeated in S.
T has length at most 200.
S and T consist of lowercase letters only.

Solution1:

Use STL to solve this question.

1
2
3
4
5
6
7
8
class Solution {
public:
    string customSortString(string S, string T) {
        sort(T.begin(), T.end(),
             [&](char a, char b) { return S.find(a) < S.find(b); });
        return T;
    }
};

time complexity: $O(nlogn)$
space complexity: $O(1)$

Solution2:

S: customer order
T: string to be sorted

  1. Use bucket sort to store all the characters in bucket.
  2. Walk through customer order, the bucket[c] contains the number of occurrence in T. We need to append that many times of c in the result string.
  3. Append remaining characters in result string. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string customSortString(string S, string T) {
        /*
        bucket sort
        1. put the string into the bucket
        2. append every same character into string
        */
        //S: cba
        //T: abcd
        vector<int> bucket(26, 0);
        for(auto c: T)
            bucket[c-'a']++;
        
        string res= "";
        for(auto c: S){
            for(int i= 0; i< bucket[c-'a']; i++){
                res+= c;
            }
            bucket[c-'a']= 0;
        }
        
        for(int i= 0; i< bucket.size(); i++){
            for(int j= 0; j< bucket[i]; j++)
                res+= (i+'a');
        }
        
        return res;
    }
};

Clarify: what if remaining characters in target not in source?

1
2
3
4
5
example: 
source: "cba"
target: "abcdeed"

would the result be "cbaddee" OR "cbadeed"?
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def customSortString(self, order: str, s: str) -> str:
        counter = Counter(s)
        res = []
        for c in order:
            if c in counter:
                res.extend([c]*counter[c])
                counter.pop(c)
        
        for k,v in counter.items():
            res.extend(k*v)
        return ''.join(res)

time complexity: $O(n)$
space complexity: $O(n)$
reference:
https://goo.gl/Lef54y
https://goo.gl/aX25f1