43-Custom-Sort-String.md

Custom Sort String

Problem Link

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

---

Pattern

• String
• Hash Table

---

Approach

Count characters in s, then build result following order string with available characters.

---

Time Complexity

O(n + m)

Space Complexity

O(1)

---

Java Solution

import java.util.*;
class Solution {
    public String customSortString(String order, String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        StringBuilder ans = new StringBuilder();
        for (char c : order.toCharArray()) {
            for (int i = 0; i < count[c - 'a']; i++) ans.append(c);
            count[c - 'a'] = 0;
        }
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < count[i]; j++) ans.append((char)('a' + i));
        }
        return ans.toString();
    }
}