For each string, let’s put the character count into an array (‘a’ -> 0, ‘b’ -> 1, etc). Now, if we iterate these arrays together and maintain two sums corresponding to each array. If the sum for string 1 is greater than sum from string 2 at any point, it means that there is a permutation such that s1<s2 alphabetically. Consider this example:
s1 = "bacc"
s2 = "accc"
Corresponding arrays:
arr1 = [1, 1, 2, 0, 0, ...]
arr2 = [1, 0, 3, 0, 0, ...]
When we iterate over these arrays, at index 2, count1 = 2 but count2 = 1. Clearly we can see that "abcc"<"accc".
Now, given that we know sum for string 1 has exceeded sum for string 2 at some point. If at any later point we find that sum for string 1 is less than sum from string 2 then there would be no such permutation where s1 < s2 or vice-versa. Similarly, we code for when sum for string 2 exceeds sum for string 1. The code below is self explanatory.
class Solution {
public boolean checkIfCanBreak(String s1, String s2) {
int n = s1.length();
int[] arr = new int[26], brr = new int[26];
for(int i = 0; i < n; i++) arr[s1.charAt(i) - 97]++;
for(int i = 0; i < n; i++) brr[s2.charAt(i) - 97]++;
int count1 = 0, count2 = 0;
boolean f1 = false, f2 = false;
for(int i = 0; i < 26; i++) {
count1 += arr[i];
count2 += brr[i];
if(count1 > count2) {
if(f2) return false;
f1 = true;
} else if(count2 > count1) {
if(f1) return false;
f2 = true;
}
}
return true;
}
}
Time complexity: O(n)
Space complexity: O(n)