We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check If a String Can Break Another String

Number: 1530

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two strings, s1 and s2, of the same length, determine if some permutation of s1 can "break" some permutation of s2 or vice versa. A string x can break string y if, after reordering, for every index i (0 ≤ i < n), the character x[i] is greater than or equal to y[i] in alphabetical order.

Key Insights

  • Sorting the strings gives the lexicographically smallest permutation.
  • Once the strings are sorted, you only need one pass to compare characters at each index.
  • Evaluate both possibilities: s1 breaking s2 and s2 breaking s1.
  • Use greedy comparison to check if either sorted s1 is element-wise greater than or equal to sorted s2 or vice-versa.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the strings. Space Complexity: O(n) for storing the sorted versions of the strings.

Solution

The algorithm sorts both strings, ensuring we compare the "best-case" orderings for the break condition. After sorting, iterate through both arrays simultaneously and check two conditions:

  1. If every character in sorted s1 is greater than or equal to the corresponding character in sorted s2.
  2. If every character in sorted s2 is greater than or equal to the corresponding character in sorted s1. If either condition holds true, one string can break the other. This approach leverages the greedy concept that sorting captures the optimal order for the break condition.

Code Solutions

def checkIfCanBreak(s1: str, s2: str) -> bool:
    # Sort both strings to obtain the smallest lexicographical permutation.
    sorted_s1 = sorted(s1)
    sorted_s2 = sorted(s2)

    # Initialize flags for both possibilities.
    s1_breaks_s2 = True
    s2_breaks_s1 = True

    # Compare each corresponding character.
    for ch1, ch2 in zip(sorted_s1, sorted_s2):
        if ch1 < ch2:
            s1_breaks_s2 = False  # s1 cannot break s2 at this position.
        if ch2 < ch1:
            s2_breaks_s1 = False  # s2 cannot break s1 at this position.
    
    # Return true if either condition holds.
    return s1_breaks_s2 or s2_breaks_s1

# Example usage:
print(checkIfCanBreak("abc", "xya"))  # Output: True
← Back to All Questions