|
| 1 | +##1. Custom Comparator |
| 2 | + |
| 3 | +::tabs-start |
| 4 | + |
| 5 | +```python |
| 6 | +classSolution: |
| 7 | +defcustomSortString(self,order:str,s:str) ->str: |
| 8 | + rank= {c: ifor i, cinenumerate(order)} |
| 9 | +return''.join(sorted(s,key=lambdac: rank.get(c,26))) |
| 10 | +``` |
| 11 | + |
| 12 | +```java |
| 13 | +publicclassSolution { |
| 14 | +publicStringcustomSortString(Stringorder,Strings) { |
| 15 | +int[] rank=newint[26]; |
| 16 | +for (int i=0; i< order.length(); i++) { |
| 17 | + rank[order.charAt(i)-'a']= i+1; |
| 18 | + } |
| 19 | + |
| 20 | +Character[] arr=newCharacter[s.length()]; |
| 21 | +for (int i=0; i< s.length(); i++) { |
| 22 | + arr[i]= s.charAt(i); |
| 23 | + } |
| 24 | + |
| 25 | +Arrays.sort(arr, (a, b)-> rank[a-'a']- rank[b-'a']); |
| 26 | + |
| 27 | +StringBuilder sb=newStringBuilder(); |
| 28 | +for (char c: arr) { |
| 29 | + sb.append(c); |
| 30 | + } |
| 31 | +return sb.toString(); |
| 32 | + } |
| 33 | +} |
| 34 | +``` |
| 35 | + |
| 36 | +```cpp |
| 37 | +classSolution { |
| 38 | +public: |
| 39 | + string customSortString(string order, string s) { |
| 40 | + vector<int> rank(26, 26); |
| 41 | + for (int i = 0; i < order.size(); ++i) { |
| 42 | + rank[order[i] - 'a'] = i; |
| 43 | + } |
| 44 | + |
| 45 | + sort(s.begin(), s.end(), [&](char a, char b) { |
| 46 | + return rank[a - 'a'] < rank[b - 'a']; |
| 47 | + }); |
| 48 | + |
| 49 | + return s; |
| 50 | +} |
| 51 | +}; |
| 52 | +``` |
| 53 | + |
| 54 | +```javascript |
| 55 | +classSolution { |
| 56 | +/** |
| 57 | + *@param{string}order |
| 58 | + *@param{string}s |
| 59 | + *@return{string} |
| 60 | +*/ |
| 61 | +customSortString(order,s) { |
| 62 | +constrank= {}; |
| 63 | +for (let i=0; i<order.length; i++) { |
| 64 | + rank[order[i]]= i; |
| 65 | + } |
| 66 | + |
| 67 | +return [...s].sort((a,b)=> { |
| 68 | +constra= rank[a]??26; |
| 69 | +constrb= rank[b]??26; |
| 70 | +return ra- rb; |
| 71 | + }).join(''); |
| 72 | + } |
| 73 | +} |
| 74 | +``` |
| 75 | +
|
| 76 | +```csharp |
| 77 | +publicclassSolution { |
| 78 | +public stringCustomSortString(stringorder,strings) { |
| 79 | + Dictionary<char, int> rank=newDictionary<char, int>(); |
| 80 | +for (int i=0; i<order.Length; i++) { |
| 81 | + rank[order[i]]= i; |
| 82 | + } |
| 83 | + |
| 84 | + char[] arr=s.ToCharArray(); |
| 85 | +Array.Sort(arr, (a,b)=> { |
| 86 | + int ra=rank.ContainsKey(a)? rank[a]:26; |
| 87 | + int rb=rank.ContainsKey(b)? rank[b]:26; |
| 88 | +return ra- rb; |
| 89 | + }); |
| 90 | + |
| 91 | +returnnewstring(arr); |
| 92 | + } |
| 93 | +} |
| 94 | +``` |
| 95 | +
|
| 96 | +::tabs-end |
| 97 | +
|
| 98 | +### Time & Space Complexity |
| 99 | +
|
| 100 | +* Time complexity: $O(n\log n)$ |
| 101 | +* Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm. |
| 102 | +
|
| 103 | +--- |
| 104 | +
|
| 105 | +## 2. Frequency Count |
| 106 | +
|
| 107 | +::tabs-start |
| 108 | +
|
| 109 | +```python |
| 110 | +classSolution: |
| 111 | + defcustomSortString(self, order: str, s: str)-> str: |
| 112 | + count= [0]*26 |
| 113 | +for cin s: |
| 114 | + count[ord(c)-ord('a')]+=1 |
| 115 | + |
| 116 | + res= [] |
| 117 | +for cin order: |
| 118 | + idx=ord(c)-ord('a') |
| 119 | +while count[idx]: |
| 120 | +res.append(c) |
| 121 | + count[idx]-=1 |
| 122 | + |
| 123 | +for idxinrange(26): |
| 124 | + c=chr(ord('a')+ idx) |
| 125 | +while count[idx]: |
| 126 | + count[idx]-=1 |
| 127 | +res.append(c) |
| 128 | + |
| 129 | +return''.join(res) |
| 130 | +``` |
| 131 | +
|
| 132 | +```java |
| 133 | +publicclassSolution { |
| 134 | +publicStringcustomSortString(Stringorder,Strings) { |
| 135 | + int[] count=newint[26]; |
| 136 | +for (char c:s.toCharArray()) { |
| 137 | + count[c-'a']++; |
| 138 | + } |
| 139 | + |
| 140 | + StringBuilder res=newStringBuilder(); |
| 141 | +for (char c:order.toCharArray()) { |
| 142 | + int idx= c-'a'; |
| 143 | +while (count[idx]>0) { |
| 144 | +res.append(c); |
| 145 | + count[idx]--; |
| 146 | + } |
| 147 | + } |
| 148 | + |
| 149 | +for (int idx=0; idx<26; idx++) { |
| 150 | + char c= (char) ('a'+ idx); |
| 151 | +while (count[idx]>0) { |
| 152 | +res.append(c); |
| 153 | + count[idx]--; |
| 154 | + } |
| 155 | + } |
| 156 | + |
| 157 | +returnres.toString(); |
| 158 | + } |
| 159 | +} |
| 160 | +``` |
| 161 | +
|
| 162 | +```cpp |
| 163 | +classSolution { |
| 164 | +public: |
| 165 | + stringcustomSortString(stringorder,strings) { |
| 166 | + vector<int>count(26,0); |
| 167 | +for (char c: s) { |
| 168 | + count[c-'a']++; |
| 169 | + } |
| 170 | + |
| 171 | + string res; |
| 172 | +for (char c: order) { |
| 173 | + int idx= c-'a'; |
| 174 | +while (count[idx]>0) { |
| 175 | + res+= c; |
| 176 | + count[idx]--; |
| 177 | + } |
| 178 | + } |
| 179 | + |
| 180 | +for (int idx=0; idx<26;++idx) { |
| 181 | + char c='a'+ idx; |
| 182 | +while (count[idx]>0) { |
| 183 | + res+= c; |
| 184 | + count[idx]--; |
| 185 | + } |
| 186 | + } |
| 187 | + |
| 188 | +return res; |
| 189 | + } |
| 190 | +}; |
| 191 | +``` |
| 192 | +
|
| 193 | +```javascript |
| 194 | +classSolution { |
| 195 | +/** |
| 196 | + *@param{string}order |
| 197 | + *@param{string}s |
| 198 | + *@return{string} |
| 199 | +*/ |
| 200 | +customSortString(order,s) { |
| 201 | +constcount=newArray(26).fill(0); |
| 202 | +for (let cof s) { |
| 203 | + count[c.charCodeAt(0)-97]++; |
| 204 | + } |
| 205 | + |
| 206 | +constres= []; |
| 207 | +for (let cof order) { |
| 208 | +let idx=c.charCodeAt(0)-97; |
| 209 | +while (count[idx]>0) { |
| 210 | +res.push(c); |
| 211 | + count[idx]--; |
| 212 | + } |
| 213 | + } |
| 214 | + |
| 215 | +for (let idx=0; idx<26; idx++) { |
| 216 | +let c=String.fromCharCode(97+ idx); |
| 217 | +while (count[idx]>0) { |
| 218 | +res.push(c); |
| 219 | + count[idx]--; |
| 220 | + } |
| 221 | + } |
| 222 | + |
| 223 | +returnres.join(''); |
| 224 | + } |
| 225 | +} |
| 226 | +``` |
| 227 | +
|
| 228 | +```csharp |
| 229 | +publicclassSolution { |
| 230 | +public stringCustomSortString(stringorder,strings) { |
| 231 | + int[] count=newint[26]; |
| 232 | +foreach (charcins) { |
| 233 | + count[c-'a']++; |
| 234 | + } |
| 235 | + |
| 236 | + StringBuilder res=newStringBuilder(); |
| 237 | +foreach (charcinorder) { |
| 238 | + int idx= c-'a'; |
| 239 | +while (count[idx]>0) { |
| 240 | +res.Append(c); |
| 241 | + count[idx]--; |
| 242 | + } |
| 243 | + } |
| 244 | + |
| 245 | +for (int idx=0; idx<26; idx++) { |
| 246 | + char c= (char)('a'+ idx); |
| 247 | +while (count[idx]>0) { |
| 248 | +res.Append(c); |
| 249 | + count[idx]--; |
| 250 | + } |
| 251 | + } |
| 252 | + |
| 253 | +returnres.ToString(); |
| 254 | + } |
| 255 | +} |
| 256 | +``` |
| 257 | +
|
| 258 | +::tabs-end |
| 259 | +
|
| 260 | +### Time & Space Complexity |
| 261 | +
|
| 262 | +* Time complexity: $O(n)$ |
| 263 | +* Space complexity: $O(n)$ |