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.
In this approach, the key idea is that by sorting both strings, you can easily determine if one can break the other by simply comparing them position by position. The sorted order ensures that if one element in s1_sorted is greater than or equal to the corresponding element in s2_sorted, then any permutation of s1 can be mapped to a permutation of s2.
To implement this, follow these steps:
s1 and s2.s1_sorted can break s2_sorted by verifying if each character in s1_sorted[i] is greater than or equal to s2_sorted[i].s2_sorted can break s1_sorted.true; otherwise, return false.The C solution sorts both strings using qsort and then compares the characters at each position. Two boolean variables track whether s1 can break s2 or vice versa.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in-place.
This approach takes advantage of counting the frequency of each character in both strings. By using arrays to count the occurrences of each character (since there are only 26 lowercase English letters), you can directly compare these arrays to determine if one string can break the other.
The steps are as follows:
true; otherwise, return false.The C solution counts character occurrences in frequency arrays for both strings and compares cumulative sums to decide if one can break the other.
Time Complexity: O(n + 26) = O(n) for counting and comparing.
Space Complexity: O(1) due to fixed-size frequency arrays.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting and Comparison Approach | Time Complexity: O(n log n) due to sorting. |
| Counting Frequency Approach | Time Complexity: O(n + 26) = O(n) for counting and comparing. |
| Default Approach | — |
| 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 |
Check If a String Can Break Another String • Fraz • 2,220 views views
Watch 8 more video solutions →Practice Check If a String Can Break Another String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor