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.

1// This is a conceptual illustration and will Time Limit Exceed.2class Solution {3    public boolean checkIfCanBreak(String s1, String s2) {4        // This is not a practical solution due to N! complexity.5        // The generation of permutations is complex and omitted for brevity.6        // List<String> perms1 = generatePermutations(s1);7        // List<String> perms2 = generatePermutations(s2);8        //9        // for (String p1 : perms1) {10        //     for (String p2 : perms2) {11        //         if (canBreak(p1, p2) || canBreak(p2, p1)) {12        //             return true;13        //         }14        //     }15        // }16        return false; // Placeholder for the logic17    }18 19    private boolean canBreak(String a, String b) {20        for (int i = 0; i < a.length(); i++) {21            if (a.charAt(i) < b.charAt(i)) {22                return false;23            }24        }25        return true;26    }27}

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.

A key insight is that if any permutation of s1 can break a permutation of s2, then the alphabetically sorted version of s1 must be able to break the alphabetically sorted version of s2. This simplifies the problem from checking (n!)² pairs to checking just one pair of sorted strings.

Algorithm

1. Convert s1 into a character array arr1.
1. Convert s2 into a character array arr2.
1. Sort arr1 in non-decreasing order.
1. Sort arr2 in non-decreasing order.
1. Define a helper function canBreak(a, b) that checks if string a can break string b. It iterates from i = 0 to n-1 and returns false if a[i] < b[i] for any i. If the loop completes, it returns true.
1. Return the result of canBreak(arr1, arr2) || canBreak(arr2, arr1).

Walkthrough

The problem asks if there exists any permutation. To make the condition x[i] >= y[i] as easy to satisfy as possible, we should pair the smallest characters of one string with the smallest of the other, the second smallest with the second smallest, and so on. This is achieved by sorting both strings. Let sorted_s1 be the string s1 with its characters sorted alphabetically, and sorted_s2 be the sorted version of s2. The problem then reduces to checking two conditions:

Can s1 break s2? We check if sorted_s1[i] >= sorted_s2[i] for all i.
Can s2 break s1? We check if sorted_s2[i] >= sorted_s1[i] for all i. If either of these conditions holds true, the function returns true. Otherwise, it returns false. The implementation involves converting the strings to character arrays, sorting them, and then iterating through them to perform the checks.

1import java.util.Arrays;2 3class Solution {4    public boolean checkIfCanBreak(String s1, String s2) {5        char[] arr1 = s1.toCharArray();6        char[] arr2 = s2.toCharArray();7 8        Arrays.sort(arr1);9        Arrays.sort(arr2);10 11        return canBreak(arr1, arr2) || canBreak(arr2, arr1);12    }13 14    private boolean canBreak(char[] arrA, char[] arrB) {15        for (int i = 0; i < arrA.length; i++) {16            if (arrA[i] < arrB[i]) {17                return false;18            }19        }20        return true;21    }22}

Complexity

Time

O(n log n). The dominant operation is sorting the two character arrays of length `n`. The final linear scans take `O(n)`.

Space

O(n). In Java, `toCharArray()` creates new arrays of size `n`. Some sorting algorithms might also use space (e.g., `O(log n)` for quicksort stack, `O(n)` for mergesort).

Trade-offs

Pros

Drastically more efficient than the brute-force approach.
Relatively simple to implement using standard library sorting functions.

Cons

The time complexity is dominated by sorting, which is O(n log n). This can be improved upon.
Requires O(n) extra space for the character arrays in Java.

This is the most efficient approach, leveraging the fact that the input strings consist of a limited character set (lowercase English letters). It uses frequency arrays and a single pass to check the break conditions in linear time, avoiding the O(n log n) cost of sorting.

Algorithm

1. Initialize two integer arrays, count1 and count2, of size 26 to all zeros.
1. Iterate through s1 and s2 to populate the frequency counts. For each character c in s1, increment count1[c - 'a']. Do similarly for s2 and count2.
1. Initialize two boolean flags, s1_breaks_s2 = true and s2_breaks_s1 = true.
1. Initialize two integer variables for prefix sums, s1_sum = 0 and s2_sum = 0.
1. Loop from i = 0 to 25 (representing characters 'a' to 'z').
1. In each iteration, update the prefix sums: s1_sum += count1[i] and s2_sum += count2[i].
1. Check the break conditions using the prefix sums:
- If s1_sum > s2_sum, then s2 cannot break s1. Set s2_breaks_s1 = false.
- If s2_sum > s1_sum, then s1 cannot break s2. Set s1_breaks_s2 = false.
1. After the loop, return s1_breaks_s2 || s2_breaks_s1.

Walkthrough

The core insight is that s2 can break s1 if and only if for every character c from 'a' to 'z', the count of characters in s1 less than or equal to c is less than or equal to the count of characters in s2 less than or equal to c. A similar condition holds for s1 breaking s2. This can be checked efficiently using prefix sums of character frequency counts. The algorithm is as follows:

Create two frequency arrays, count1 and count2, of size 26.
Populate these arrays by iterating through s1 and s2, which takes O(n) time.
We then check two possibilities simultaneously: if s1 can break s2, and if s2 can break s1.
We iterate from i = 0 to 25 (for 'a' to 'z'), maintaining running prefix sums of the counts. Let these be s1_sum and s2_sum.
In each iteration, if s1_sum becomes greater than s2_sum, it violates the condition for s2 breaking s1. If s2_sum becomes greater than s1_sum, it violates the condition for s1 breaking s2.
If after checking all characters, at least one of the two "break" possibilities remains true, we return true. Otherwise, false.

1class Solution {2    public boolean checkIfCanBreak(String s1, String s2) {3        int n = s1.length();4        int[] count1 = new int[26];5        int[] count2 = new int[26];6 7        for (int i = 0; i < n; i++) {8            count1[s1.charAt(i) - 'a']++;9            count2[s2.charAt(i) - 'a']++;10        }11 12        boolean s1BreaksS2 = true;13        boolean s2BreaksS1 = true;14 15        int s1PrefixSum = 0;16        int s2PrefixSum = 0;17 18        for (int i = 0; i < 26; i++) {19            s1PrefixSum += count1[i];20            s2PrefixSum += count2[i];21 22            // Condition for s2 to break s1 is prefix_sum(s1) <= prefix_sum(s2)23            if (s1PrefixSum > s2PrefixSum) {24                s2BreaksS1 = false;25            }26            27            // Condition for s1 to break s2 is prefix_sum(s2) <= prefix_sum(s1)28            if (s2PrefixSum > s1PrefixSum) {29                s1BreaksS2 = false;30            }31        }32 33        return s1BreaksS2 || s2BreaksS1;34    }35}

Complexity

Time

O(n + k), where `n` is the length of the strings and `k` is the alphabet size (26). Since `k` is constant, this simplifies to `O(n)`.

Space

O(k), where `k` is the alphabet size (26). This is constant space, so `O(1)`.

Trade-offs

Pros

Optimal time complexity of O(n) as it only requires a few linear passes.
Constant space complexity O(1) as the frequency arrays are of fixed size (26).
Most efficient solution for the given constraints.

Cons

The logic involving prefix sums is slightly less intuitive than direct sorting.
This approach is specialized for inputs with a small, fixed character set.

Solutions

Solution

1class Solution {2public3  boolean checkIfCanBreak(String s1, String s2) {4    char[] cs1 = s1.toCharArray();5    char[] cs2 = s2.toCharArray();6    Arrays.sort(cs1);7    Arrays.sort(cs2);8    return check(cs1, cs2) || check(cs2, cs1);9  }10private11  boolean check(char[] cs1, char[] cs2) {12    for (int i = 0; i < cs1.length; ++i) {13      if (cs1[i] < cs2[i]) {14        return false;15      }16    }17    return true;18  }19}

1class Solution {2public:3  bool checkIfCanBreak(string s1, string s2) {4    sort(s1.begin(), s1.end());5    sort(s2.begin(), s2.end());6    return check(s1, s2) || check(s2, s1);7  }8  bool check(string &s1, string &s2) {9    for (int i = 0; i < s1.size(); ++i) {10      if (s1[i] < s2[i]) {11        return false;12      }13    }14    return true;15  }16};

1class Solution:2    def checkIfCanBreak(self, s1: str, s2: str) -> bool: cs1 = sorted(s1) cs2 = sorted(s2) return all(a >= b for a, b in zip(cs1, cs2)) or all(a <= b for a, b in zip(cs1, cs2))

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 problem

Solution

1class Solution {2public3  boolean checkIfCanBreak(String s1, String s2) {4    char[] cs1 = s1.toCharArray();5    char[] cs2 = s2.toCharArray();6    Arrays.sort(cs1);7    Arrays.sort(cs2);8    return check(cs1, cs2) || check(cs2, cs1);9  }10private11  boolean check(char[] cs1, char[] cs2) {12    for (int i = 0; i < cs1.length; ++i) {13      if (cs1[i] < cs2[i]) {14        return false;15      }16    }17    return true;18  }19}

1class Solution {2public:3  bool checkIfCanBreak(string s1, string s2) {4    sort(s1.begin(), s1.end());5    sort(s2.begin(), s2.end());6    return check(s1, s2) || check(s2, s1);7  }8  bool check(string &s1, string &s2) {9    for (int i = 0; i < s1.size(); ++i) {10      if (s1[i] < s2[i]) {11        return false;12      }13    }14    return true;15  }16};

1class Solution:2    def checkIfCanBreak(self, s1: str, s2: str) -> bool: cs1 = sorted(s1) cs2 = sorted(s2) return all(a >= b for a, b in zip(cs1, cs2)) or all(a <= b for a, b in zip(cs1, cs2))

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.