Formatted question description: https://leetcode.ca/all/1433.html

1433. Check If a String Can Break Another String

Level

Medium

Description

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:

  • s1.length == n
  • s2.length == n
  • 1 <= n <= 10^5
  • All strings consist of lowercase English letters.

Solution

Convert s1 and s2 into arrays of type char, which are array1 and array2 respectively, and sort array1 and array2. Then compare each pair of characters in array1 and array2. If there exists two indices i and j such that array1[i] < array2[i] and array1[j] > array2[j], then return false. Otherwise, return true.

class Solution {
    public boolean checkIfCanBreak(String s1, String s2) {
        char[] array1 = s1.toCharArray();
        char[] array2 = s2.toCharArray();
        Arrays.sort(array1);
        Arrays.sort(array2);
        int difference = 0;
        int length = array1.length;
        for (int i = 0; i < length; i++) {
            int curDifference = array1[i] - array2[i];
            if (curDifference != 0) {
                curDifference /= Math.abs(curDifference);
                if (curDifference * difference < 0)
                    return false;
                else
                    difference = curDifference;
            }
        }
        return true;
    }
}

All Problems

All Solutions