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 == ns2.length == n1 <= 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;
}
}