Check If a String Can Break Another String: Sorted Comparison Pattern

Given two strings s1 and s2 of the same length, a string x "breaks" string y if x[i] >= y[i] for every index i (in alphabetical order after rearranging). Return True if s1 can break s2 or s2 can break s1, otherwise return False.

This is LeetCode 1433: Check If a String Can Break Another String. It is a clean example of how sorting transforms a messy comparison problem into something you can solve with a single pass.

Why this problem matters

At first glance, it seems like you would need to check all possible rearrangements of each string to see if one can dominate the other. That would be factorial time, which is clearly not going to work for strings up to length 100,000.

The key observation is that if any rearrangement of s1 can break any rearrangement of s2, then the sorted version of s1 can break the sorted version of s2. Sorting is the greedy choice: it pairs the smallest characters against the smallest, giving each position the best chance of satisfying the >= condition. Once you sort both strings, a single left-to-right scan tells you the answer.

The approach

1. Sort both strings.
2. Compare character by character. Check if sorted s1[i] >= s2[i] at every position. If so, s1 breaks s2.
3. Also check the reverse: whether sorted s2[i] >= s1[i] at every position.
4. Return True if either direction works.

You can do both checks in a single pass by tracking two boolean flags.

The solution

def check_if_can_break(s1: str, s2: str) -> bool:
    s1_sorted = sorted(s1)
    s2_sorted = sorted(s2)

    s1_breaks = True
    s2_breaks = True

    for a, b in zip(s1_sorted, s2_sorted):
        if a < b:
            s1_breaks = False
        if b < a:
            s2_breaks = False

    return s1_breaks or s2_breaks

Let's walk through what each piece does.

First, you sort both strings. This is the critical step. Sorting ensures that you are comparing characters in the most favorable alignment. If any permutation of s1 can break any permutation of s2, then the sorted permutation will also work.

The two boolean flags, s1_breaks and s2_breaks, start as True. As you scan through the sorted characters in parallel, any position where s1's character is strictly less than s2's character means s1 cannot break s2 (so flip s1_breaks to False). Similarly, any position where s2's character is strictly less flips s2_breaks.

At the end, if at least one flag is still True, the answer is True. If both flags have been flipped to False, neither string can break the other.

Visual walkthrough

Let's trace through the example s1 = "abc", s2 = "xya" step by step. Watch how sorting reveals the answer immediately.

After sorting, the comparison becomes mechanical. You just check each position from left to right. No backtracking, no permutations, no recursion.

Complexity analysis

Time is O(n log n) where n is the length of the strings. Sorting dominates the cost. The comparison loop is O(n), which is absorbed into the sorting term.

Space is O(n) because sorted() creates a new list. If you sort in place (for example, by converting to a list, sorting, and iterating), the space is still O(n) due to the list conversion. In languages with mutable strings you could sort in place for O(1) extra space, but the time complexity stays the same.

The building blocks

1. Sort-and-compare for greedy string problems

The pattern of sorting both inputs before comparing them position by position:

s1_sorted = sorted(s1)
s2_sorted = sorted(s2)
for a, b in zip(s1_sorted, s2_sorted):
    if a < b:
        return False
return True

This is a general technique for problems that ask "can one sequence dominate another in some rearrangement?" Sorting gives you the optimal alignment, and a single scan confirms or denies the claim. You will see this same idea in problems like "Advantage Shuffle" (LeetCode 870) where you sort both arrays to greedily match elements.

2. Dual-flag tracking in a single pass

The pattern of tracking two conditions simultaneously to avoid running two separate loops:

flag_a = True
flag_b = True
for x, y in zip(seq_a, seq_b):
    if not condition_a(x, y):
        flag_a = False
    if not condition_b(x, y):
        flag_b = False
return flag_a or flag_b

This is useful any time you need to check "does direction A work OR does direction B work?" Instead of writing two loops, you fold both checks into one. The result is cleaner code and the same O(n) scan. You can even add an early exit: if both flags are already False, break out of the loop.

Edge cases

Before submitting, think through these scenarios:

• Identical strings: s1 == s2. Every character ties, so both s1_breaks and s2_breaks remain True. Return True.
• Single character strings: s1 = "a", s2 = "b". After sorting, b >= a is True, so s2 breaks s1. Return True.
• All same characters: s1 = "aaa", s2 = "aaa". Every position ties. Return True.
• Completely reversed dominance: s1 = "zzz", s2 = "aaa". s1 breaks s2 trivially. Return True.
• Anagram inputs: s1 = "ab", s2 = "ba". After sorting, both become "ab". Every position ties, so >= holds in both directions. Return True.
• True neither-breaks case: s1 = "cb", s2 = "ad". Sorted: s1 = "bc", s2 = "ad". For s1 breaking s2: b >= a (yes) but c >= d (no). For s2 breaking s1: a >= b (no). Neither direction holds at every position. Return False.

From understanding to recall

You have seen the full pattern: sort both strings, scan once with two flags, return the result. The logic is simple and the code is short. But writing it correctly under pressure requires that you remember the details. Do you check >= or >? Do you need both directions or just one? Do you return and or or?

These are not conceptual gaps. They are recall gaps. Spaced repetition closes them. You practice writing the sort-and-compare pattern and the dual-flag loop from memory at increasing intervals. After a few rounds, you do not need to think about it. You see "can one string dominate another in some arrangement" and the template flows out automatically.

Related posts

• Valid Anagram - The frequency counting pattern for comparing character compositions of two strings
• Custom Sort String - Another sorting-based string problem where character ordering determines the solution
• Sort Colors - The Dutch National Flag algorithm, another example of how sorting strategy drives the solution

CodeBricks breaks Check If a String Can Break Another String into its sort-and-compare and dual-flag building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy string problem shows up in your interview, you do not hesitate. You just write it.