Algorithm
Problem Name: 791. Custom Sort String
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 = "cbafg", s = "abcd" Output: "cbad"
Constraints:
1 <= order.length <= 261 <= s.length <= 200orderandsconsist of lowercase English letters.- All the characters of
orderare unique.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string customSortString(string S, string T) {
string res = "";
vector<int>v(26);
for(auto c: T) v[c - 'a']++;
for(auto c: S)
while(v[c - 'a']--) res.push_back(c);
for(int i = 0; i < 26; i++)
while(v[i]-- > 0) res.push_back('a' + i);
return res;
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String customSortString(String order, String s) {
Map frequency = new HashMap<>();
for (char c : s.toCharArray()) {
frequency.put(c, frequency.getOrDefault(c, 0) + 1);
}
StringBuilder sb = new StringBuilder();
for (char c : order.toCharArray()) {
int count = frequency.getOrDefault(c, 0);
while (count-- > 0) {
sb.append(c);
}
frequency.put(c, 0);
}
for (Character key : frequency.keySet()) {
int count = frequency.getOrDefault(key, 0);
while (count-- > 0) {
sb.append(key);
}
}
return sb.toString();
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const customSortString = function(S, T) {
const arr = [];
const remaining = [];
const hash = {};
for (let i = 0; i < S.length; i++) {
if (T.indexOf(S.charAt(i)) !== -1) {
arr.push(S.charAt(i));
}
}
let char;
for (let j = 0; j < T.length; j++) {
char = T.charAt(j);
if (arr.indexOf(char) === -1 && remaining.indexOf(char) === -1) {
remaining.push(char);
}
hash[char] = hash.hasOwnProperty(char) ? hash[char] + 1 : 1;
}
return `${genPart(arr, hash)}${genPart(remaining, hash)}`;
};
function constructStr(char, num) {
let str = "";
for (let i = 0; i < num; i++) {
str += char;
}
return str;
}
function genPart(arr, hash) {
return arr.reduce((ac, el) => {
return ac + constructStr(el, hash[el]);
}, "");
}
console.log(customSortString("kqep", "pekeq"));
console.log(
customSortString(
"hucw",
"utzoampdgkalexslxoqfkdjoczajxtuhqyxvlfatmptqdsochtdzgypsfkgqwbgqbcamdqnqztaqhqanirikahtmalzqjjxtqfnh"
)
);
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def customSortString(self, S, T):
"""
:type S: str
:type T: str
:rtype: str
"""
t = set(T)
t2 = set(S)
from collections import Counter as ct
c = ct(T)
s = [char * c[char] for char in S if char in t]
add = [char * c[char] for char in t - t2]
return "".join(s + add)
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
using System.Text;
namespace LeetCode
{
public class _0791_CustomSortString
{
public string CustomSortString(string S, string T)
{
var counts = new int[26];
foreach (var ch in T)
counts[ch - 'a']++;
var sb = new StringBuilder();
foreach (var ch in S)
{
sb.Append(ch, counts[ch - 'a']);
counts[ch - 'a'] = 0;
}
for (char ch = 'a'; ch < = 'z'; ch++)
sb.Append(ch, counts[ch - 'a']);
return sb.ToString();
}
}
}
Input
Output