Given two strings: s1 and s2 with the same size, check if some permutation of string s1 can break some permutation of string s2 or vice-versa (in other words s2 can break s1).
A string x can break string y (both of size n) if x[i] >= y[i] (in alphabetical order) for all i between 0 and n-1.
Example 1:
Input: s1 = "abc", s2 = "xya"
Output: true
Explanation: "ayx" is a permutation of s2="xya" which can break to string "abc" which is a permutation of s1="abc".
Example 2:
Input: s1 = "abe", s2 = "acd"
Output: false
Explanation: All permutations for s1="abe" are: "abe", "aeb", "bae", "bea", "eab" and "eba" and all permutation for s2="acd" are: "acd", "adc", "cad", "cda", "dac" and "dca". However, there is not any permutation from s1 which can break some permutation from s2 and vice-versa.
class Solution {
public boolean checkIfCanBreak(String s1, String s2) {
TreeMap<Character, Integer> map1 = new TreeMap();
for (char c : s1.toCharArray()) {
map1.putIfAbsent(c, 0);
map1.put(c, map1.get(c) + 1);
}
boolean canBreak = true;
for (char c : s2.toCharArray()) {
Character breaker = map1.ceilingKey(c);
if (breaker == null) {
canBreak = false;
break;
} else {
map1.put(breaker, map1.get(breaker) - 1);
if (map1.get(breaker) == 0) map1.remove(breaker);
}
}
if (canBreak) return true;
TreeMap<Character, Integer> map2 = new TreeMap();
for (char c : s2.toCharArray()) {
map2.putIfAbsent(c, 0);
map2.put(c, map2.get(c) + 1);
}
canBreak = true;
for (char c : s1.toCharArray()) {
Character breaker = map2.ceilingKey(c);
if (breaker == null) {
canBreak = false;
break;
} else {
map2.put(breaker, map2.get(breaker) - 1);
if (map2.get(breaker) == 0) map2.remove(breaker);
}
}
return canBreak;
}
}
Since we have a constraint that all the characters are in lowercase English letters. This quickly should strike us through the counting sort algorithm.
We fill in the buckets of each string by counting each occurrence of the character.
We traverse the buckets of both s1, s2 and increment the sums of each occurrence. While we traverse, the count of the lower string(count1) will be first incremented than the larger string count(count2).
Count1 > count2 indicates, s1 is smaller than s2. Vice versa, count2 > count1 indicates s2 is smaller than s1.
From here, we should check that count1 >= count2 for all rest of indices until we reach index = 26.
If not, we return false. Explanation with an example:
Step-2: Traverse s1-buckets and s2-buckets and increment count1 and count2.
At index = 0: count1 = 1, count2 = 0. (Since s1 started with a and s2 started with b). So s1 is smaller than s2. We enable boolean for s1 saying s1 is shorter.
At index = 1: count1 = 2, count2 = 1
At index = 2: count1 = 2, count2 = 2. (By this point we have crossed, (ab*, bc*) & s1Shorter = true..
At index = 3: count1 = 2, count2 = 3, with count2 > count1: it implies s2 is lexicographically smaller than S1, which contradicts with point-1(index=0). So we return false.
public boolean checkIfCanBreak(String s1, String s2) {
int[] s1Bucket = new int[26];
int[] s2Bucket = new int[26];
int index = 0, count1 = 0, count2 = 0;
boolean smallerS1 = false, smallerS2 = false;
for (int i = 0; i < s1.length(); i++) {
s1Bucket[s1.charAt(i) - 'a']++;
s2Bucket[s2.charAt(i) - 'a']++;
}
for (int i = 0; i < 26; i++) {
count1 += s1Bucket[i];
count2 += s2Bucket[i];
if (count1 > count2) {
if (smallerS2) {
return false;
}
smallerS1 = true;
}
else if (count2 > count1) {
if (smallerS1) {
return false;
}
smallerS2 = true;
}
}
return true;
}