| 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.
| Input | Output |
|---|---|
| order = “cba”, s = “abcd” | cbad |
| order = “cbafg”, s = “abcd” | cbad |
| order = “cbafg”, s = “aabcccdfg” | cccbaafgd |
| order = “cba”, s = “aabcccdfg” | cccbaadgf or cccbaagdf (last elements order does not matter) |
Notes
- Keep a hashmap for count of chars from s, eg a - 2, b - 1 , c-3, d - 1, f- 1, g-1 on 4th example
- Now loop through ‘order’, and check for each element of o, on our hashmap what was our key’s value.
- If key exists, then append x times to our string builder, eg - append c 3 times.
- Once we append, on that loop remove the key
- Continue through all.
- At the end if hashmap is not empty, then we have to append remaining chars to our stringbuilder
- Return the stringBuilder.toString()
Note- Instead of hashmap we could also use array of 26 chars, where we would write the count on corresponding index. (2nd solution below)
Time Complexity - O(length of s) since we have to max scan through whole of s | Space Complexity - Same as time
class Solution {
public String customSortString(String order, String s) {
HashMap<Character, Integer> hashMap = new HashMap<>();
StringBuilder str = new StringBuilder();
for(char ch: s.toCharArray()) {
hashMap.put(ch, hashMap.getOrDefault(ch, 0)+1);
}
for (char o: order.toCharArray()) {
if (hashMap.containsKey(o)) {
while (hashMap.get(o) > 0) {
str.append(o);
hashMap.replace(o, hashMap.get(o) - 1);
}
}
}
//remaining keys with > 0 just gets added at the end
for (char key : hashMap.keySet()) {
while (hashMap.get(key) > 0) {
str.append(key);
hashMap.replace(key, hashMap.get(key) - 1);
}
}
return str.toString();
}
}
class Solution {
public String customSortString(String order, String s) {
int[] count = new int[26];
StringBuilder str = new StringBuilder();
for (char ch : s.toCharArray()) {
// ch -'a' gets us the index, we +1 before adding a value to the index
// since its count of occurence
// ch - 'a' when char is a is 0,
// ch - 'a' when char is d is 3
//System.out.println("Char " + ch + " :" + (ch-'a'));
++count[ch - 'a'];
}
//count of 'abcdg' = [1,1,1,1,0,0,1,0...0 (till 26)]
for (char c : order.toCharArray()) {
// while we found the count of char c (-- we are doing -- opposite to above doing ++ )is > 0
while (count[c - 'a']-- > 0) {
str.append(c);
}
}
// remaining items we loop from a to z since count had 26 chars
// if original count for 'abcdg' = [1,1,1,1,0,0,1,0...0 (till 26)]
// order was cba
// at this point, count = [0,0,0,1,0,0,1,0...0 (till 26)]
for (char c = 'a'; c <= 'z'; ++c) {
while (count[c - 'a']-- > 0) {
str.append(c);
}
}
return str.toString();
}
}
| Valid Number | 
A valid number can be split up into these components (in order): A decimal number or an integer. (Optional) An ‘e’ or ‘E’, followed by an integer. A decimal number can be split up into these components (in order): (Optional) A sign character (either ‘+’ or ‘-‘). One of the following formats: One or more digits, followed by a dot ‘.’. One or more digits,...
read more
| Simplify Path | Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path. “/a/./” –> means stay at the current directory ‘a’ “/a/b/..” –> means jump to the parent directory from ‘b’ to ‘a’ ”////” –> consecutive multiple ‘/’ are a valid path, they are equivalent to...
read more