Check If a String Can Break Another String

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.

Example 3:

Input: s1 = "leetcodee", s2 = "interview"
Output: true

 

Constraints:


Solution:

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;
    }
}



S1 = "abe", S2 = "bcd"". (Expected: false)


  1. 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.
  2. At index = 1:
    count1 = 2, count2 = 1
  3. At index = 2:
    count1 = 2, count2 = 2. (By this point we have crossed, (ab*, bc*) & s1Shorter = true..
  4. 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;
    }