Custom Sort String solution and explanation
Google
9 more videos on this problem
CUSTOM SORT STRING | PYTHON | LEETCODE # 791Cracking FAANG · 10:33 · 9K views
Custom Sort String | 2 Approaches | Intuition | Meta | Leetcode 791codestorywithMIK · 28:33 · 7K views
Custom Sort String || Leetcode 791 || 1 Variant & Follow-up Question Meta Actually AsksCoding with Minmer · 22:00 · 5K views
791. Custom Sort String | 2 Approaches | Custom Comparator | Hash MapAryan Mittal · 11:17 · 3K views
Custom Sort String | Leetcode 791 | Live coding sessionCoding Decoded · 7:22 · 2K views
Leetcode | 791. Custom Sort String | Medium | JavaDeveloper Docs · 6:29 · 974 views
Leetcode 791: Custom Sort String | Java SolutionMaybe Something New · 8:46 · 755 views
791. Custom Sort String - English VersionSimple Code - 단순코드 · 8:31 · 563 views
Custom Sort String | LeetCode 791 | Coders CampCoders Camp · 6:47 · 433 views
Daily Leetcode #1441: Mar 11, 2024 - 791. Custom Sort StringProgramming Live with Larry · 3:48 · 388 views
The problem
You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously.
Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.
Return any permutation of s that satisfies this property.
Example 1:
Input: order = "cba", s = "abcd"
Output: "cbad"
Explanation: "a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".
Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.
Example 2:
Input: order = "bcafg", s = "abcd"
Output: "bcad"
Explanation: The characters "b", "c", and "a" from order dictate the order for the characters in s. The character "d" in s does not appear in order, so its position is flexible.
Following the order of appearance in order, "b", "c", and "a" from s should be arranged as "b", "c", "a". "d" can be placed at any position since it's not in order. The output "bcad" correctly follows this rule. Other arrangements like "dbca" or "bcda" would also be valid, as long as "b", "c", "a" maintain their order.
Constraints:
1 <= order.length <= 261 <= s.length <= 200orderandsconsist of lowercase English letters.- All the characters of
orderare unique.
Approach overview
Problem Overview: You receive two strings: order and s. The characters in order define the required priority. Rearrange characters in s so they follow this custom order. Characters not present in order can appear anywhere after the ordered ones.
Approach 1: Counting Sort with Frequency Map (O(n + m) time, O(1) space)
This approach treats the problem like a constrained counting sort. First build a frequency table for characters in s using a simple array or hash table. Then iterate through each character in order and append it to the result as many times as its frequency indicates. After processing all characters in order, append the remaining characters from the frequency map that were not specified in the custom order.
The key insight is that you never need to compare characters directly. The custom order already defines the sequence. Counting occurrences lets you reconstruct the string in linear time. Because the alphabet size is fixed (typically 26 lowercase letters), the extra memory is constant. This method is essentially a specialized form of sorting optimized for character frequencies.
Approach 2: Sorting with Custom Comparator (O(n log n) time, O(n) space)
This approach leverages a standard sorting algorithm but modifies how characters are compared. First build a lookup table that maps each character in order to its index. Then convert the string s into a list and sort it using a custom comparator or key function. During comparison, characters with lower order indices come first. Characters not present in order can be assigned a default large index so they naturally move to the end.
This method uses built-in sorting utilities and keeps the implementation straightforward. The algorithm repeatedly compares characters using the custom ranking, which leads to O(n log n) time complexity. It relies on concepts from string manipulation and custom sorting logic. The approach is useful when adapting to problems where frequency counting is not feasible or when the ordering rule becomes more complex.
Recommended for interviews: The counting sort approach is the expected solution. It achieves linear time by avoiding comparisons and directly reconstructing the result using frequency counts. Interviewers often accept the comparator-based solution first since it demonstrates understanding of custom sorting, but the counting strategy shows stronger algorithmic optimization and awareness of fixed character constraints.
Approach 1: Counting Sort Approach
This approach involves counting the occurrence of each character in string s and then constructing the result string by iterating through characters in order, followed by any characters in s that do not appear in order. This ensures the output string follows the custom order defined.
from collections import Counter
def customSortString(order: str, s: str) -> str:
count = Counter(s)
result = []
for char in order:
if char in count:
result.append(char * count[char])
del count[char]
for char, cnt in count.items():
result.append(char * cnt)
return ''.join(result)
order = "cba"
s = "abcd"
print(customSortString(order, s))import java.util.HashMap;
public class CustomSortString {
public String customSortString(String order, String s) {
HashMap<Character, Integer> countMap = new HashMap<>();
for (char c : s.toCharArray()) {
countMap.put(c, countMap.getOrDefault(c, 0) + 1);
}
StringBuilder result = new StringBuilder();
for (char c : order.toCharArray()) {
if (countMap.containsKey(c)) {
for (int i = 0; i < countMap.get(c); i++) {
result.append(c);
}
countMap.remove(c);
}
}
for (char c : countMap.keySet()) {
for (int i = 0; i < countMap.get(c); i++) {
result.append(c);
}
}
return result.toString();
}
public static void main(String[] args) {
CustomSortString sorter = new CustomSortString();
String order = "cba";
String s = "abcd";
System.out.println(sorter.customSortString(order, s));
}
}#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
string customSortString(string order, string s) {
unordered_map<char, int> countMap;
for (char c : s) {
countMap[c]++;
}
string result;
for (char c : order) {
result.append(countMap[c], c);
countMap.erase(c);
}
for (auto &[c, count] : countMap) {
result.append(count, c);
}
return result;
}
int main() {
string order = "cba";
string s = "abcd";
cout << customSortString(order, s) << endl;
return 0;
}function customSortString(order, s) {
let count = {};
for (let char of s) {
count[char] = (count[char] || 0) + 1;
}
let result = '';
for (let char of order) {
if (count[char]) {
result += char.repeat(count[char]);
delete count[char];
}
}
for (let char in count) {
result += char.repeat(count[char]);
}
return result;
}
let order = "cba";
let s = "abcd";
console.log(customSortString(order, s));#include <stdio.h>
#include <string.h>
char* customSortString(char* order, char* s) {
int freq[26] = {0};
for (int i = 0; s[i]; i++) {
freq[s[i] - 'a']++;
}
int idx = 0;
static char result[201];
for (int i = 0; order[i]; i++) {
while (freq[order[i] - 'a']-- > 0) {
result[idx++] = order[i];
}
}
for (int i = 0; i < 26; i++) {
while (freq[i]-- > 0) {
result[idx++] = 'a' + i;
}
}
result[idx] = '\0';
return result;
}
int main() {
char order[] = "cba";
char s[] = "abcd";
printf("%s\n", customSortString(order, s));
return 0;
}using System;
using System.Text;
using System.Collections.Generic;
class CustomSortStringClass {
public string CustomSortString(string order, string s) {
Dictionary<char, int> countMap = new Dictionary<char, int>();
foreach (char c in s) {
if (countMap.ContainsKey(c))
countMap[c]++;
else
countMap[c] = 1;
}
StringBuilder result = new StringBuilder();
foreach (char c in order) {
if (countMap.ContainsKey(c)) {
result.Append(c, countMap[c]);
countMap.Remove(c);
}
}
foreach (var item in countMap) {
result.Append(item.Key, item.Value);
}
return result.ToString();
}
static void Main() {
CustomSortStringClass css = new CustomSortStringClass();
string order = "cba";
string s = "abcd";
Console.WriteLine(css.CustomSortString(order, s));
}
}This Python solution uses the Counter class to store character frequencies from s. It builds the result string using characters from order, then adds any leftover characters from s. Finally, it joins the list of characters into a string.
Time Complexity: O(n + m).
Space Complexity: O(n).
Approach 2: Sorting with Custom Comparator
This approach involves sorting the string s using a custom comparator function derived from the order string. You respect the sequence provided in order and sort the characters of s accordingly.
def customSortString(order: str, s: str) -> str:
priority = {char: i for i, char in enumerate(order)}
sorted_s = sorted(s, key=lambda x: priority.get(x, 26))
return ''.join(sorted_s)
order = "cba"
s = "abcd"
print(customSortString(order, s))import java.util.*;
public class CustomSortStringWithComparator {
public String customSortString(String order, String s) {
Map<Character, Integer> priority = new HashMap<>();
for (int i = 0; i < order.length(); i++) {
priority.put(order.charAt(i), i);
}
Character[] characters = new Character[s.length()];
for (int i = 0; i < s.length(); i++) {
characters[i] = s.charAt(i);
}
Arrays.sort(characters, (a, b) -> priority.getOrDefault(a, 26) - priority.getOrDefault(b, 26));
StringBuilder result = new StringBuilder();
for (char c : characters) {
result.append(c);
}
return result.toString();
}
public static void main(String[] args) {
CustomSortStringWithComparator sorter = new CustomSortStringWithComparator();
String order = "cba";
String s = "abcd";
System.out.println(sorter.customSortString(order, s));
}
}#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
using namespace std;
string customSortString(string order, string s) {
unordered_map<char, int> priority;
for (int i = 0; i < order.size(); i++) {
priority[order[i]] = i;
}
sort(s.begin(), s.end(), [&](char a, char b) {
return priority[a] < priority[b];
});
return s;
}
int main() {
string order = "cba";
string s = "abcd";
cout << customSortString(order, s) << endl;
return 0;
}function customSortString(order, s) {
let priority = {};
for (let i = 0; i < order.length; i++) {
priority[order[i]] = i;
}
let sorted_s = [...s].sort((a, b) => (priority[a] || 26) - (priority[b] || 26));
return sorted_s.join('');
}
let order = "cba";
let s = "abcd";
console.log(customSortString(order, s));In this Python solution, a dictionary assigns each character in order a priority value. Using the sorted() function with a custom key, the string s is reordered according to the priorities.
Time Complexity: O(n log n).
Space Complexity: O(n) for the dictionary and the list created during sorting.
Approach 3: Default Approach
function customSortString(order: string, s: string): string {
const toIndex = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
const n = order.length;
const d = new Array(26).fill(n);
for (let i = 0; i < n; i++) {
d[toIndex(order[i])] = i;
}
return [...s].sort((a, b) => d[toIndex(a)] - d[toIndex(b)]).join('');
}func customSortString(order string, s string) string {
d := [26]int{}
for i := range order {
d[order[i]-'a'] = i
}
cs := []byte(s)
sort.Slice(cs, func(i, j int) bool { return d[cs[i]-'a'] < d[cs[j]-'a'] })
return string(cs)
}impl Solution {
pub fn custom_sort_string(order: String, s: String) -> String {
let n = order.len();
let mut d = [n; 26];
for (i, c) in order.as_bytes().iter().enumerate() {
d[(c - b'a') as usize] = i;
}
let mut ans = s.chars().collect::<Vec<_>>();
ans.sort_by(|&a, &b| {
d[((a as u8) - ('a' as u8)) as usize].cmp(&d[((b as u8) - ('a' as u8)) as usize])
});
ans.into_iter().collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Counting Sort Approach | Time Complexity: O(n + m). |
| Sorting with Custom Comparator | Time Complexity: O(n log n). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Sort with Frequency Map | O(n + m) | O(1) | Best general solution when characters come from a limited alphabet |
| Sorting with Custom Comparator | O(n log n) | O(n) | Useful when relying on built-in sorting or when ordering rules are more flexible |
Frequently asked questions
Is Custom Sort String easy or hard?
Custom Sort String is generally considered a medium difficulty problem. The challenge lies in recognizing that direct sorting is unnecessary and that a frequency counting strategy can produce a linear-time solution.
Custom Sort String Python/Java solution
Python and Java implementations typically use a frequency map or array to count characters. The algorithm then iterates through the order string to rebuild the result. Both languages can implement the counting approach in O(n) time with minimal extra memory.
How to solve Custom Sort String in O(n)?
Use a frequency array or hash map to count characters in s. Iterate through the order string and append characters based on their counts. Finally append any remaining characters not included in order. Each character is processed once, giving O(n + m) complexity.
What is the best approach for Custom Sort String?
The counting sort approach using a frequency map is the most efficient solution. Count occurrences of each character in the input string, then rebuild the result by iterating through the custom order string. This avoids comparisons and runs in linear time O(n + m).
Is Custom Sort String asked at Google/Amazon/Meta?
Custom ordering and frequency-based sorting problems commonly appear in interviews at companies like Amazon, Google, and Meta. Variations of this question test understanding of hash tables, counting techniques, and custom sorting logic.
What data structure is used in Custom Sort String?
A hash table or fixed-size frequency array is the main data structure used in the optimal solution. It stores the count of each character in the string and allows quick reconstruction according to the custom order.
What is the time complexity of Custom Sort String?
The optimal solution runs in O(n + m) time, where n is the length of string s and m is the length of the order string. The algorithm counts character frequencies and reconstructs the string according to the given order.