LeetCode : 791. Custom Sort String

[congr]

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

[congr]

O(NLogN)

class Solution {
    public String customSortString(String S, String T) {
        int[] s = new int[128];
        Arrays.fill(s, Integer.MAX_VALUE);
        for (int i = 0; i<S.length(); i++)
            s[S.charAt(i)] = i;

        Character[] t = new Character[T.length()];
        int k = 0;
        for (char c : T.toCharArray()) t[k++] = c; 

        Arrays.sort(t, (a,b) -> s[a] - s[b]);

        k =0;
        char[] res = new char[T.length()];
        for (Character c: t) res[k++] = c;
        return String.valueOf(res);
    }
}

[congr]

2ms, faster than 100%

class Solution {
    public String customSortString(String S, String T) {
        char[] ch = new char[26];
        for (char c : T.toCharArray()) ch[c-'a']++;

        StringBuilder sb = new StringBuilder();
        for (char c : S.toCharArray()) {
            for (int i = 0; i < ch[c-'a']; i++) sb.append(c);
            ch[c-'a'] = 0;
        }

        for (int i = 0; i < 26; i++)
            for (int j = 0; j < ch[i]; j++) 
                sb.append((char)('a'+i)); // !!!(char)

        return sb.toString();
    }
}

[congr]

The easiest for me, but it's much slower

class Solution {
    public String customSortString(String S, String T) {
        Map<Character, Integer> map = new HashMap();
        for (char t : T.toCharArray()) map.merge(t, 1, Integer::sum);

        StringBuilder sb = new StringBuilder();
        for (char s : S.toCharArray()) {
            int cnt = map.getOrDefault(s, 0); // S: "cbafg", T: "abcd"
            while (cnt-- > 0) sb.append(s);
            map.put(s, 0); 
        }

        for (Character c : map.keySet()) {
            int cnt = map.get(c);
            while (cnt-- > 0) sb.append(c);
        }

        return sb.toString();
    }
}

[congr]

more readable code with Array.

class Solution {
    public String customSortString(String S, String T) {
        StringBuilder sb = new StringBuilder();

        int[] ch = new int[26]; // !!! int[]

        for (char c : T.toCharArray()) ch[c-'a']++;

        for (char c : S.toCharArray()) {
            while (ch[c-'a']-- > 0) sb.append(c);
        }

        for (char c : T.toCharArray()) {
            while (ch[c-'a']-- > 0) sb.append(c);
        }

        return sb.toString();
    }
}