Problem

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 or vice-versa.

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.

Examples

Example 1:

1
2
3

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:

1
2
3

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:

1
2

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

Solution

Method 1 - Sorting

To determine if one permutation of s1 can break one permutation of s2 or vice versa, we need to sort both strings and compare them character by character. Here are the detailed steps:

  • Sort the characters of both strings.
  • Compare the sorted strings to check if one can break the other.
  • To break s2, every character in the sorted s1 should be greater than or equal to the corresponding character in the sorted s2.
  • Similarly, check if s2 can break s1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    public boolean checkIfCanBreak(String s1, String s2) {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        
        boolean canBreak1 = true;
        boolean canBreak2 = true;
        
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] < arr2[i]) {
                canBreak1 = false;
            }
            if (arr2[i] < arr1[i]) {
                canBreak2 = false;
            }
        }
        
        return canBreak1 || canBreak2;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def checkIfCanBreak(self, s1: str, s2: str) -> bool:
        arr1 = sorted(s1)
        arr2 = sorted(s2)
        
        can_break_1 = True
        can_break_2 = True
        
        for i in range(len(arr1)):
            if arr1[i] < arr2[i]:
                can_break_1 = False
            if arr2[i] < arr1[i]:
                can_break_2 = False
                
        return can_break_1 or can_break_2

Complexity

  • ⏰ Time complexity: O(n log n) for sorting both strings.
  • 🧺 Space complexity: O(n) for storing the sorted versions of the strings.