LeetCode 791: Custom Sort String (Frequency Buckets + Ordered Emit)
LeetCode 791Hash TableStringToday we solve LeetCode 791 - Custom Sort String.
Source: https://leetcode.com/problems/custom-sort-string/
English
Problem Summary
We are given an ordering string order (all unique chars) and a target string s. We must permute s so that characters appearing in order follow that relative order. Characters not in order can appear anywhere after that.
Key Insight
Count each character frequency in s, then:
- Emit characters following order, each repeated by its count.
- Emit all remaining characters (not listed in order).
This guarantees every ordered character appears in the required relative order while preserving multiplicities.
Algorithm Steps
1) Build frequency table freq from s.
2) For each char c in order, append c exactly freq[c] times, then clear freq[c].
3) Iterate over all letters, append remaining counts.
4) Return the built string.
Complexity Analysis
Time: O(|order| + |s| + A), where A=26 for lowercase letters.
Space: O(A).
Common Pitfalls
- Forgetting to append leftover characters not in order.
- Appending ordered characters but not decreasing/clearing counts, causing duplicates.
- Using generic sort with custom comparator when counting is simpler and faster here.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String customSortString(String order, String s) {
int[] freq = new int[26];
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i) - 'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < order.length(); i++) {
int idx = order.charAt(i) - 'a';
while (freq[idx]-- > 0) sb.append((char) (idx + 'a'));
freq[idx] = 0;
}
for (int i = 0; i < 26; i++) {
while (freq[i]-- > 0) sb.append((char) (i + 'a'));
}
return sb.toString();
}
}func customSortString(order string, s string) string {
freq := make([]int, 26)
for i := 0; i < len(s); i++ {
freq[s[i]-'a']++
}
out := make([]byte, 0, len(s))
for i := 0; i < len(order); i++ {
idx := order[i] - 'a'
for freq[idx] > 0 {
out = append(out, order[i])
freq[idx]--
}
}
for i := 0; i < 26; i++ {
for freq[i] > 0 {
out = append(out, byte('a'+i))
freq[i]--
}
}
return string(out)
}class Solution {
public:
string customSortString(string order, string s) {
vector freq(26, 0);
for (char c : s) freq[c - 'a']++;
string ans;
ans.reserve(s.size());
for (char c : order) {
int idx = c - 'a';
while (freq[idx]-- > 0) ans.push_back(c);
freq[idx] = 0;
}
for (int i = 0; i < 26; i++) {
while (freq[i]-- > 0) ans.push_back(char('a' + i));
}
return ans;
}
}; class Solution:
def customSortString(self, order: str, s: str) -> str:
freq = [0] * 26
for ch in s:
freq[ord(ch) - ord('a')] += 1
out = []
for ch in order:
idx = ord(ch) - ord('a')
out.append(ch * freq[idx])
freq[idx] = 0
for i in range(26):
if freq[i] > 0:
out.append(chr(ord('a') + i) * freq[i])
return "".join(out)/**
* @param {string} order
* @param {string} s
* @return {string}
*/
var customSortString = function(order, s) {
const freq = new Array(26).fill(0);
for (const ch of s) freq[ch.charCodeAt(0) - 97]++;
const out = [];
for (const ch of order) {
const idx = ch.charCodeAt(0) - 97;
while (freq[idx] > 0) {
out.push(ch);
freq[idx]--;
}
}
for (let i = 0; i < 26; i++) {
while (freq[i] > 0) {
out.push(String.fromCharCode(97 + i));
freq[i]--;
}
}
return out.join('');
};中文
题目概述
给定顺序字符串 order（字符不重复）和字符串 s，需要把 s 重新排列，使得凡是出现在 order 中的字符，其相对顺序满足 order 的定义；不在 order 里的字符可放在后面任意位置。
核心思路
先统计 s 每个字符出现次数，再两段输出：
- 第一段按 order 顺序输出，对应字符按频次重复。
- 第二段输出剩余未处理字符。
这样既满足自定义顺序，也不会丢失或重复字符。
算法步骤
1）统计 s 的频次数组 freq。
2）遍历 order，把当前字符输出 freq[c] 次并清零。
3）遍历 26 个字母，输出剩余频次。
4）拼接后返回结果字符串。
复杂度分析
时间复杂度：O(|order| + |s| + 26)。
空间复杂度：O(26)。
常见陷阱
- 忘记处理不在 order 里的剩余字符。
- 按 order 输出后不清零，导致重复输出。
- 直接用排序比较器实现，代码更复杂且不如计数直观。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String customSortString(String order, String s) {
int[] freq = new int[26];
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i) - 'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < order.length(); i++) {
int idx = order.charAt(i) - 'a';
while (freq[idx]-- > 0) sb.append((char) (idx + 'a'));
freq[idx] = 0;
}
for (int i = 0; i < 26; i++) {
while (freq[i]-- > 0) sb.append((char) (i + 'a'));
}
return sb.toString();
}
}func customSortString(order string, s string) string {
freq := make([]int, 26)
for i := 0; i < len(s); i++ {
freq[s[i]-'a']++
}
out := make([]byte, 0, len(s))
for i := 0; i < len(order); i++ {
idx := order[i] - 'a'
for freq[idx] > 0 {
out = append(out, order[i])
freq[idx]--
}
}
for i := 0; i < 26; i++ {
for freq[i] > 0 {
out = append(out, byte('a'+i))
freq[i]--
}
}
return string(out)
}class Solution {
public:
string customSortString(string order, string s) {
vector freq(26, 0);
for (char c : s) freq[c - 'a']++;
string ans;
ans.reserve(s.size());
for (char c : order) {
int idx = c - 'a';
while (freq[idx]-- > 0) ans.push_back(c);
freq[idx] = 0;
}
for (int i = 0; i < 26; i++) {
while (freq[i]-- > 0) ans.push_back(char('a' + i));
}
return ans;
}
}; class Solution:
def customSortString(self, order: str, s: str) -> str:
freq = [0] * 26
for ch in s:
freq[ord(ch) - ord('a')] += 1
out = []
for ch in order:
idx = ord(ch) - ord('a')
out.append(ch * freq[idx])
freq[idx] = 0
for i in range(26):
if freq[i] > 0:
out.append(chr(ord('a') + i) * freq[i])
return "".join(out)/**
* @param {string} order
* @param {string} s
* @return {string}
*/
var customSortString = function(order, s) {
const freq = new Array(26).fill(0);
for (const ch of s) freq[ch.charCodeAt(0) - 97]++;
const out = [];
for (const ch of order) {
const idx = ch.charCodeAt(0) - 97;
while (freq[idx] > 0) {
out.push(ch);
freq[idx]--;
}
}
for (let i = 0; i < 26; i++) {
while (freq[i] > 0) {
out.push(String.fromCharCode(97 + i));
freq[i]--;
}
}
return out.join('');
};
Comments