# Check If a String Can Break Another String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-a-string-can-break-another-string)
Canonical: https://scaleengineer.com/dsa/problems/check-if-a-string-can-break-another-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** String
---
## 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`.

**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
## Brute Force by Generating All Permutations
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.
**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.
**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.
### Explanation
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.

```java
// 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;
    }
}
```
### Algorithm
- 1. Generate all unique permutations of string `s1`. Store them in a list `perms1`.
- 2. Generate all unique permutations of string `s2`. Store them in a list `perms2`.
- 3. Iterate through each permutation `p1` in `perms1`.
- 4. Inside this loop, iterate through each permutation `p2` in `perms2`.
- 5. Check if `p1` can break `p2`. This is done by comparing characters at each index `i`: `p1[i] >= p2[i]`.
- 6. If `p1` breaks `p2`, return `true`.
- 7. Check if `p2` can break `p1`. This is done by comparing characters at each index `i`: `p2[i] >= p1[i]`.
- 8. If `p2` breaks `p1`, return `true`.
- 9. If the loops complete without finding a valid pair, return `false`.

## Sorting Characters
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.
**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).
**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.
### Explanation
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: 
1. Can `s1` break `s2`? We check if `sorted_s1[i] >= sorted_s2[i]` for all `i`.
2. 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.

```java
import java.util.Arrays;

class Solution {
    public boolean checkIfCanBreak(String s1, String s2) {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();

        Arrays.sort(arr1);
        Arrays.sort(arr2);

        return canBreak(arr1, arr2) || canBreak(arr2, arr1);
    }

    private boolean canBreak(char[] arrA, char[] arrB) {
        for (int i = 0; i < arrA.length; i++) {
            if (arrA[i] < arrB[i]) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- 1. Convert `s1` into a character array `arr1`.
- 2. Convert `s2` into a character array `arr2`.
- 3. Sort `arr1` in non-decreasing order.
- 4. Sort `arr2` in non-decreasing order.
- 5. 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`.
- 6. Return the result of `canBreak(arr1, arr2) || canBreak(arr2, arr1)`.

## Optimal Frequency Counting with Prefix Sums
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.
**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)`.
**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.
### Explanation
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:
1. Create two frequency arrays, `count1` and `count2`, of size 26.
2. Populate these arrays by iterating through `s1` and `s2`, which takes `O(n)` time.
3. We then check two possibilities simultaneously: if `s1` can break `s2`, and if `s2` can break `s1`.
4. 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`.
5. 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`.
6. If after checking all characters, at least one of the two "break" possibilities remains true, we return `true`. Otherwise, `false`.

```java
class Solution {
    public boolean checkIfCanBreak(String s1, String s2) {
        int n = s1.length();
        int[] count1 = new int[26];
        int[] count2 = new int[26];

        for (int i = 0; i < n; i++) {
            count1[s1.charAt(i) - 'a']++;
            count2[s2.charAt(i) - 'a']++;
        }

        boolean s1BreaksS2 = true;
        boolean s2BreaksS1 = true;

        int s1PrefixSum = 0;
        int s2PrefixSum = 0;

        for (int i = 0; i < 26; i++) {
            s1PrefixSum += count1[i];
            s2PrefixSum += count2[i];

            // Condition for s2 to break s1 is prefix_sum(s1) <= prefix_sum(s2)
            if (s1PrefixSum > s2PrefixSum) {
                s2BreaksS1 = false;
            }
            
            // Condition for s1 to break s2 is prefix_sum(s2) <= prefix_sum(s1)
            if (s2PrefixSum > s1PrefixSum) {
                s1BreaksS2 = false;
            }
        }

        return s1BreaksS2 || s2BreaksS1;
    }
}
```
### Algorithm
- 1. Initialize two integer arrays, `count1` and `count2`, of size 26 to all zeros.
- 2. 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`.
- 3. Initialize two boolean flags, `s1_breaks_s2 = true` and `s2_breaks_s1 = true`.
- 4. Initialize two integer variables for prefix sums, `s1_sum = 0` and `s2_sum = 0`.
- 5. Loop from `i = 0` to 25 (representing characters 'a' to 'z').
- 6. In each iteration, update the prefix sums: `s1_sum += count1[i]` and `s2_sum += count2[i]`.
- 7. 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`.
- 8. After the loop, return `s1_breaks_s2 || s2_breaks_s1`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool checkIfCanBreak(string s1, string s2) {
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    return check(s1, s2) || check(s2, s1);
  }
  bool check(string &s1, string &s2) {
    for (int i = 0; i < s1.size(); ++i) {
      if (s1[i] < s2[i]) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    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))

```