Domain 2MediumMEDIUM

Check If a String Can Break Another String

Sort both strings and verify if one dominates the other element-wise in either direction.

Domain: medium•Updated: 2026-09-16
#Sorting#Greedy Algorithm#O(N log N)#O(N)

Problem Breakdown

We are asked to determine if a permutation of string s1 can break some permutation of string s2, or vice-versa. A string xx breaks string yy if for every index ii, the character in xx is greater than or equal to the corresponding character in yy.

  • Input: Two strings s1 and s2 of length nn.
  • Output: Boolean (True if one breaks the other, False otherwise).
  • Definition: Break condition: x[i]≥y[i]x[i] \ge y[i] for all indices after optimal reordering.

Intuition

A brute-force approach checking permutations is infeasible (O((N!)2)O((N!)^2)) due to factorial complexity. The key insight relies on the Greedy property of sorting. To maximize the chance that one string dominates another, we should align their smallest characters against each other. If a valid “break” relationship exists between two sets of numbers/characters, it will hold true when both are sorted in ascending order and compared element-wise.

  1. Sort s1 and s2.
  2. Check if every character in sorted s1 is ≥\ge corresponding char in sorted s2.
  3. If not, check the reverse (sorted s2 vs sorted s1).

Approach

  1. Sort both input strings alphabetically using Python’s built-in sort function. This takes O(Nlog⁡N)O(N \log N) time and returns lists of characters.
  2. Define a helper logic to compare two sorted arrays element-wise. We need to check if the first array dominates the second (element ≥\ge) for all positions.
  3. Use Python’s all() function with zip to iterate through both strings simultaneously without manual loop overhead or index management errors.
  4. Return the logical OR of the two checks: (s1 breaks s2) OR (s2 breaks s1).

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N). The dominant operation is sorting both strings (NN characters). Comparing elements takes linear time O(N)O(N), which is subsumed by the sort. Given constraints N=105N=10^5, this fits within typical limits (approx 2×1062 \times 10^6 operations for sorting vs limit of ≈108\approx 10^8 ops/sec).
  • Space Complexity: O(N)O(N). Python’s sorted() creates a new list of characters, requiring space proportional to the input size. This fits within standard memory limits (typically 256MB+).

Solution

def checkIfCanBreak(s1: str, s2: str) -> bool:
    # Sort both strings to align smallest with smallest (Greedy alignment)
    sorted_s1 = sorted(s1) 
    sorted_s2 = sorted(s2) 
    
    n = len(s1)
    
    # Check if one string dominates the other element-wise
    def check_breaker(larger, smaller):
        for c_lg, c_sm in zip(larger, smaller):
            if ord(c_lg) < ord(c_sm): 
                return False # Found a character where larger is actually smaller
        return True

    # Check s1 >= s2 OR s2 >= s1
    return check_breaker(sorted_s1, sorted_s2) or check_breaker(sorted_s2, sorted_s1)

Edge Cases Handled

  • Identical Strings: If s1 == s2, sorting yields identical lists. The comparison loop finds all characters equal (≥\ge holds), returning True. Correctly handled by the logic c≥cc \ge c.
  • Single Character Strings: Loop runs once, checks condition directly. Handled correctly.
  • All Characters Same in One String: Sorting handles duplicates naturally; comparisons remain valid regardless of duplicate positions since order doesn’t matter for equality check.
  • Maximum Length (10510^5): Python’s Timsort is efficient on partially sorted data and uses O(N)O(N) space, which fits within standard memory limits (typically 256MB+). The time complexity remains logarithmic relative to input size.