LeetCode 1433 - Check If a String Can Break Another String

The problem asks us to determine whether one string can "break" another string through some permutation. Given two strin

leetcodemediumstringgreedysorting

LeetCode Problem 1433

Difficulty: 🟡 Medium
Topics: String, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to determine whether one string can "break" another string through some permutation. Given two strings s1 and s2 of equal length, a string x can break string y if, after arranging both strings in some order, every character in x is greater than or equal to the corresponding character in y when compared alphabetically. In other words, for all indices i, x[i] >= y[i].

The input consists of two lowercase English strings of length n where 1 <= n <= 10^5. The output is a boolean indicating whether there exists a permutation of s1 that can break a permutation of s2, or vice-versa. The constraints allow strings up to 100,000 characters, so algorithms with factorial or even quadratic complexity are infeasible.

Edge cases to consider include strings where all characters are the same, strings that are already sorted in opposite orders, and strings with minimal length (n = 1). The problem guarantees that both strings are of the same length, so we do not need to handle length mismatches.

Approaches

A brute-force approach would generate all permutations of s1 and s2 and then check each pair to see if one can break the other. This approach is correct in theory because it exhaustively checks all possibilities, but the time complexity is factorial, O(n!), making it completely impractical for n up to 10^5.

The key insight is that we do not need to check all permutations. Sorting both strings provides a canonical form that preserves the relative order of characters. If a sorted version of s1 can break the sorted version of s2 at every index, then there exists some permutation of s1 that can break s2. The same logic applies in the opposite direction. This reduces the problem to simply sorting both strings and performing a linear scan to verify the break condition.

Approach Time Complexity Space Complexity Notes
Brute Force O((n!)^2) O(n!) Generate all permutations of s1 and s2 and compare each pair
Optimal O(n log n) O(n) Sort both strings and compare character by character

Algorithm Walkthrough

  1. Sort both strings: Convert s1 and s2 into sorted lists of characters. Sorting ensures that we consider the permutation that maximizes the chance of one string breaking the other.
  2. Initialize flags: Set two boolean flags, s1_can_break_s2 and s2_can_break_s1, to True. These flags will track whether s1 can break s2 and whether s2 can break s1.
  3. Compare characters: Iterate over the indices of the sorted strings. At each index i, compare s1[i] with s2[i]. If s1[i] < s2[i], then s1 cannot break s2, so set s1_can_break_s2 to False. Conversely, if s2[i] < s1[i], then s2 cannot break s1, so set s2_can_break_s1 to False.
  4. Return result: After the iteration, if either s1_can_break_s2 or s2_can_break_s1 is True, return True. Otherwise, return False.

Why it works: Sorting ensures that we consider the permutation of each string that maximizes its potential to break the other. If no sorted permutation can break the other, no other permutation can either, so this approach guarantees correctness.

Python Solution

class Solution:
    def checkIfCanBreak(self, s1: str, s2: str) -> bool:
        sorted_s1 = sorted(s1)
        sorted_s2 = sorted(s2)
        
        s1_can_break_s2 = True
        s2_can_break_s1 = True
        
        for c1, c2 in zip(sorted_s1, sorted_s2):
            if c1 < c2:
                s1_can_break_s2 = False
            if c2 < c1:
                s2_can_break_s1 = False
                
        return s1_can_break_s2 or s2_can_break_s1

This implementation sorts both strings, initializes the flags, and iterates through the characters comparing them. Using zip allows a clean one-pass iteration over the two sorted strings. If at any index one string is smaller than the other, the corresponding flag is updated. The result is returned as True if either string can break the other.

Go Solution

import "sort"

func checkIfCanBreak(s1 string, s2 string) bool {
    s1Runes := []rune(s1)
    s2Runes := []rune(s2)
    
    sort.Slice(s1Runes, func(i, j int) bool { return s1Runes[i] < s1Runes[j] })
    sort.Slice(s2Runes, func(i, j int) bool { return s2Runes[i] < s2Runes[j] })
    
    s1CanBreakS2 := true
    s2CanBreakS1 := true
    
    for i := 0; i < len(s1Runes); i++ {
        if s1Runes[i] < s2Runes[i] {
            s1CanBreakS2 = false
        }
        if s2Runes[i] < s1Runes[i] {
            s2CanBreakS1 = false
        }
    }
    
    return s1CanBreakS2 || s2CanBreakS1
}

The Go version handles strings as slices of runes for safe character comparison. Sorting is done using sort.Slice, and the iteration logic mirrors the Python implementation. Go does not have a zip equivalent, so a traditional for loop with indexing is used.

Worked Examples

Example 1: s1 = "abc", s2 = "xya"

Step sorted_s1 sorted_s2 s1_can_break_s2 s2_can_break_s1
Initial a b c a x y True True
i = 0 a vs a True True
i = 1 b vs x b < x -> False x > b -> True
i = 2 c vs y c < y -> False y > c -> True

Result: True because s2_can_break_s1 = True.

Example 2: s1 = "abe", s2 = "acd"

Step sorted_s1 sorted_s2 s1_can_break_s2 s2_can_break_s1
Initial a b e a c d True True
i = 0 a vs a True True
i = 1 b vs c b < c -> False c > b -> True
i = 2 e vs d e > d -> True d < e -> False

Result: False because both flags are False at the end.

Example 3: s1 = "leetcodee", s2 = "interview"

After sorting:

| sorted_s1 | c e e e l o t t |

| sorted_s2 | e e i n r t v w |

Iteration confirms that s2 can break s1, so result is True.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting both strings dominates the time complexity
Space O(n) Sorting creates new lists or slices of length n

Sorting is the bottleneck. The linear scan after sorting is O(n) but negligible compared to sorting. Space complexity is linear because new sorted arrays or slices are created.

Test Cases

# Provided examples
assert Solution().checkIfCanBreak("abc", "xya") == True  # s2 can break s1
assert Solution().checkIfCanBreak("abe", "acd") == False  # No permutation can break the other
assert Solution().checkIfCanBreak("leetcodee", "interview") == True  # s2 can break s1

# Edge cases
assert Solution().checkIfCanBreak("a", "a") == True  # single character, identical
assert Solution().checkIfCanBreak("a", "b") == True  # single character, s2 can break s1
assert Solution().checkIfCanBreak("b", "a") == True  # single character, s1 can break s2

# All characters same
assert Solution().checkIfCanBreak("aaa", "aaa") == True

# Opposite order
assert Solution().checkIfCanBreak("abc", "cba") == True  # s1 can break s2 after sorting

# Large case
s1 = "a"*50000 + "z"*50000
s2 = "a"*50000 + "y"*50000
assert Solution().checkIfCanBreak(s1, s2) == True  # s1 can break s2
Test Why
"abc" vs "xya"