Scale Engineer

Check If a String Can Break Another String

Med
#1326Time: O(n * (n!)^2). Generating permutations is `O(n * n!)`. We do this twice. Then we have a nested loop of size `n!` x `n!`, with an `O(n)` comparison inside.Space: O(n * n!) to store all the permutations.
Patterns
Greedy
Algorithms
Sorting
Data structures
String

Prompt

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.

 

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach literally translates the problem statement into code. It generates every possible permutation of s1 and s2 and checks if any pair of permutations satisfies the "break" condition. This method is used to establish a baseline and understand the full scope of the problem before optimizing.

Algorithm

    1. Generate all unique permutations of string s1. Store them in a list perms1.
    1. Generate all unique permutations of string s2. Store them in a list perms2.
    1. Iterate through each permutation p1 in perms1.
    1. Inside this loop, iterate through each permutation p2 in perms2.
    1. Check if p1 can break p2. This is done by comparing characters at each index i: p1[i] >= p2[i].
    1. If p1 breaks p2, return true.
    1. Check if p2 can break p1. This is done by comparing characters at each index i: p2[i] >= p1[i].
    1. If p2 breaks p1, return true.
    1. If the loops complete without finding a valid pair, return false.

Walkthrough

The core idea is to explore all (n!) * (n!) pairs of permutations. We can write a recursive helper function, say generatePermutations(string), that returns a list of all its permutations. We would call this function for both s1 and s2. Then, we use nested loops to iterate through every permutation p1 from s1's list and every permutation p2 from s2's list. Inside the loops, we check two conditions: does p1 break p2? and does p2 break p1? If either condition is met for any pair, we immediately return true. If we check all pairs and find no such case, we return false. This approach is computationally very expensive and is not feasible for the given constraints, but it demonstrates a direct, albeit naive, understanding of the problem.

// This is a conceptual illustration and will Time Limit Exceed.class Solution {    public boolean checkIfCanBreak(String s1, String s2) {        // This is not a practical solution due to N! complexity.        // The generation of permutations is complex and omitted for brevity.        // List<String> perms1 = generatePermutations(s1);        // List<String> perms2 = generatePermutations(s2);        //        // for (String p1 : perms1) {        //     for (String p2 : perms2) {        //         if (canBreak(p1, p2) || canBreak(p2, p1)) {        //             return true;        //         }        //     }        // }        return false; // Placeholder for the logic    }     private boolean canBreak(String a, String b) {        for (int i = 0; i < a.length(); i++) {            if (a.charAt(i) < b.charAt(i)) {                return false;            }        }        return true;    }}

Complexity

Time

O(n * (n!)^2). Generating permutations is `O(n * n!)`. We do this twice. Then we have a nested loop of size `n!` x `n!`, with an `O(n)` comparison inside.

Space

O(n * n!) to store all the permutations.

Trade-offs

Pros

  • Conceptually simple and directly follows the problem definition.

Cons

  • Extremely inefficient with a time complexity of O(n * (n!)^2), making it infeasible for n > 10.

  • High memory usage to store all permutations.

Solutions

class Solution {public  boolean checkIfCanBreak(String s1, String s2) {    char[] cs1 = s1.toCharArray();    char[] cs2 = s2.toCharArray();    Arrays.sort(cs1);    Arrays.sort(cs2);    return check(cs1, cs2) || check(cs2, cs1);  }private  boolean check(char[] cs1, char[] cs2) {    for (int i = 0; i < cs1.length; ++i) {      if (cs1[i] < cs2[i]) {        return false;      }    }    return true;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem