Watch 9 video solutions for Check If a String Can Break Another String, a medium level problem involving String, Greedy, Sorting. This walkthrough by Fraz has 2,220 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 == ns2.length == n1 <= n <= 10^5Problem Overview: You are given two strings of equal length. A string s1 can break s2 if after permuting both strings, every character in s1 is greater than or equal to the corresponding character in s2. The task is to determine whether either string can break the other.
Approach 1: Sorting and Comparison Approach (O(n log n) time, O(1) or O(n) space)
The key observation: if a valid permutation exists, sorting both strings gives the most favorable comparison order. Convert both strings to arrays, sort them, then compare characters index by index. If s1[i] >= s2[i] for all i, then s1 can break s2. Perform the symmetric check as well to see if s2 can break s1. Sorting ensures characters are aligned in increasing order so the greedy comparison works. This approach relies on sorting plus a simple linear scan. Time complexity is O(n log n) due to sorting, and space is O(1) if sorting in place or O(n) depending on language implementation.
Approach 2: Counting Frequency Approach (O(n) time, O(1) space)
Since characters are limited to lowercase English letters, sorting can be replaced with counting frequencies. Build two frequency arrays of size 26 for both strings. Then simulate the sorted comparison by walking from 'a' to 'z', maintaining prefix sums that represent how many characters have appeared so far. Track whether the cumulative count of one string ever becomes smaller than the other during comparison. If the ordering constraint holds for all characters, that string can break the other. This technique avoids explicit sorting and uses a greedy prefix comparison over character counts. Time complexity becomes O(n + 26) which simplifies to O(n), and space is O(1). The logic combines ideas from string processing and greedy ordering.
Recommended for interviews: The sorting approach is the most commonly expected answer. It is easy to reason about and communicates the core insight quickly: align both strings in sorted order and check dominance character by character. Mentioning the frequency-count optimization shows deeper understanding and demonstrates how to reduce the O(n log n) sorting step to O(n) using fixed alphabet constraints.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Comparison | O(n log n) | O(1) / O(n) | Best general solution; easiest to implement and explain during interviews |
| Counting Frequency | O(n) | O(1) | When alphabet size is fixed (e.g., lowercase letters) and you want to avoid sorting |