Sponsored
Sponsored
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.
Time Complexity: O(n + m), where n is the length of s and m is the length of order, since we iterate through each character of both strings.
Space Complexity: O(1), only a fixed extra space for the frequency array is used.
1import java.util.HashMap;
2
3public class CustomSortString {
4 public String customSortString(String order, String s) {
5 HashMap<Character, Integer> countMap = new HashMap<>();
6 for (char c : s.toCharArray()) {
7 countMap.put(c, countMap.getOrDefault(c, 0) + 1);
8 }
9
10 StringBuilder result = new StringBuilder();
11 for (char c : order.toCharArray()) {
12 if (countMap.containsKey(c)) {
13 for (int i = 0; i < countMap.get(c); i++) {
14 result.append(c);
15 }
16 countMap.remove(c);
17 }
18 }
19
20 for (char c : countMap.keySet()) {
21 for (int i = 0; i < countMap.get(c); i++) {
22 result.append(c);
23 }
24 }
25
26 return result.toString();
27 }
28
29 public static void main(String[] args) {
30 CustomSortString sorter = new CustomSortString();
31 String order = "cba";
32 String s = "abcd";
33 System.out.println(sorter.customSortString(order, s));
34 }
35}Using a HashMap to count character frequencies in s, the Java solution appends characters to the result string in the sequence given by order. Remaining characters are appended in no particular order afterwards.
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.
Time Complexity: O(n log n), due to the sorting operation.
Space Complexity: O(1) for map usage and additional space for sort function.
1#include <iostream>
2#include <string>
3#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;
}In this C++ solution, an unordered_map is used to assign indices as priorities based on order. The custom comparator used in the sort function rearranges s to fit these priorities.