Check If a String Can Break Another String — Solution
Check If a String Can Break Another String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check If a String Can Break Another String is a medium coding problem on strings, sorting and greedy, asked in Amazon, Adobe and Flipkart interviews.
- Difficulty: Medium
- Topics: Strings, Sorting, Greedy
- Asked at: Amazon, Adobe, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string x can break a string y if some permutation of x is at least as large as some permutation of y at every position.
Given two strings s1 and s2 of equal length, return true if either can break the other.
Example 1
Input: s1 = "abc", s2 = "xya"
Output: true
Explanation: The permutation "ayx" of s2 beats "abc" at every position.
Example 2
Input: s1 = "abe", s2 = "acd"
Output: false
Explanation: Neither ordering dominates the other everywhere.
Example 3
Input: s1 = "leetcodee", s2 = "interview"
Output: true
Constraints
s1.length == s2.length1 <= s1.length <= 100000Both strings consist of lowercase English letters.
Hints for Check If a String Can Break Another String
Hint 1
Permutations are free, so only the multiset of letters matters.
Hint 2
Sorting both strings pairs the smallest with the smallest, the second smallest with the second smallest, and so on.
Hint 3
If one string dominates at all, it dominates under that sorted pairing.
How to solve Check If a String Can Break Another String
Sort both strings and compare position by position. The sorted pairing is the best case for domination: if it fails there, no permutation can succeed.
Approach
- Sort the characters of both strings ascending.
- Sweep once, tracking two flags:
aWins(no position wherea[i] < b[i]) andbWins(no position whereb[i] < a[i]). - Return
aWins || bWins.
Why it works
Suppose some pairing has x dominating y. Sorting both and pairing in order can only improve each comparison — by an exchange argument, swapping any out-of-order pair never turns a win into a loss. So the sorted comparison is a complete test.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Testing only one direction — the statement allows either string to be the breaker.
- Bailing out of the loop on the first
a[i] < b[i]loses the chance to discover thatbbreaksa; track both flags in one pass instead.
Reference solution
Python
def checkIfCanBreak(s1: str, s2: str) -> bool:
a = sorted(s1)
b = sorted(s2)
a_wins = all(x >= y for x, y in zip(a, b))
b_wins = all(y >= x for x, y in zip(a, b))
return a_wins or b_winsJava
public static boolean checkIfCanBreak(String s1, String s2) {
char[] a = s1.toCharArray();
char[] b = s2.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
boolean aWins = true, bWins = true;
for (int i = 0; i < a.length; i++) {
if (a[i] < b[i]) aWins = false;
if (b[i] < a[i]) bWins = false;
}
return aWins || bWins;
}C++
bool checkIfCanBreak(string s1, string s2) {
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
bool aWins = true, bWins = true;
for (size_t i = 0; i < s1.size(); i++) {
if (s1[i] < s2[i]) aWins = false;
if (s2[i] < s1[i]) bWins = false;
}
return aWins || bWins;
}JavaScript
var checkIfCanBreak = function(s1, s2) {
var a = s1.split("").sort();
var b = s2.split("").sort();
var aWins = true, bWins = true;
for (var i = 0; i < a.length; i++) {
if (a[i] < b[i]) aWins = false;
if (b[i] < a[i]) bWins = false;
}
return aWins || bWins;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Sorting Algorithms