Check If a String Can Break Another String — Medium Problem & Solution

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.length
• 1 <= s1.length <= 100000
• Both strings consist of lowercase English letters.

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

1. Sort the characters of both strings ascending.
2. Sweep once, tracking two flags: aWins (no position where a[i] < b[i]) and bWins (no position where b[i] < a[i]).
3. 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 that b breaks a; 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_wins

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium