In this guide, you will get 791. Custom Sort String LeetCode Solution with the best time and space complexity. The solution to Custom Sort String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
1 <= order.length <= 26
1 <= s.length <= 200
order and s consist of lowercase English letters.
All the characters of order are unique.
Complexity Analysis
Time Complexity: O(|\texttt{order}| + |\texttt{s}|)
Space Complexity: O(26)
791. Custom Sort String LeetCode Solution in C++
class Solution {
public:
string customSortString(string order, string s) {
string ans;
vector<int> count(128);
for (const char c : s)
++count[c];
for (const char c : order)
while (count[c]-- > 0)
ans += c;
for (char c = 'a'; c <= 'z'; ++c)
while (count[c]-- > 0)
ans += c;
return ans;
}
}; /* code provided by PROGIEZ */
791. Custom Sort String LeetCode Solution in Java
class Solution {
public String customSortString(final String order, final String s) {
StringBuilder sb = new StringBuilder();
int[] count = new int[128];
for (final char c : s.toCharArray())
++count[c];
for (final char c : order.toCharArray())
while (count[c]-- > 0)
sb.append(c);
for (char c = 'a'; c <= 'z'; ++c)
while (count[c]-- > 0)
sb.append(c);
return sb.toString();
}
} // code provided by PROGIEZ
791. Custom Sort String LeetCode Solution in Python
class Solution:
def customSortString(self, order: str, s: str) -> str:
ans = ""
count = [0] * 26
for c in s:
count[string.ascii_lowercase.index(c)] += 1
for c in order:
while count[string.ascii_lowercase.index(c)] > 0:
ans += c
count[string.ascii_lowercase.index(c)] -= 1
for c in string.ascii_lowercase:
for _ in range(count[string.ascii_lowercase.index(c)]):
ans += c
return ans # code by PROGIEZ
