Check If a String Can Break Another String

Check If a String Can Break Another String - Problem

Given two strings s1 and s2 with the same length, check if some permutation of string s1 can break some permutation of string s2 or vice-versa.

A string x can break string y (both of size n) if x[i] >= y[i] (in alphabetical order) for all i between 0 and n-1.

Return true if either s1 can break s2 or s2 can break s1, otherwise return false.

Input & Output

Example 1 — One String Can Break Another

$ Input: s1 = "abc", s2 = "xya"

› Output: true

💡 Note: We can arrange s2 as "yxa" (descending) and s1 as "abc" (ascending). Since y≥a, x≥b, but a

Example 2 — Neither Can Break

$ Input: s1 = "abe", s2 = "acd"

› Output: false

💡 Note: Best case for s1: "eba" vs s2: "acd" → e≥a✓, b≥c✗. Best case for s2: "dca" vs s1: "abe" → d≥a✓, c≥b✓, a≥e✗. Neither arrangement allows one string to completely break the other.

Example 3 — Identical Characters

$ Input: s1 = "leetcode", s2 = "interview"

› Output: true

💡 Note: Sort s1 descending: "toeelcde" vs s2 ascending: "eeiinrtv". Check position by position to see if s1 can break s2, or try the reverse arrangement.

Constraints

s1.length == s2.length
1 ≤ s1.length ≤ 10⁵
All strings consist of lowercase English characters only.

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings of equal length with different character arrangements

Optimal Sorting

Sort to maximize one string's advantage over the other

Character Comparison

Check if all positions satisfy the breaking condition

Key Takeaway

🎯 Key Insight: Sort strings optimally to test the best-case scenario for each breaking direction

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use a greedy approach with sorting. To check if s1 can break s2, sort s1 in descending order and s2 in ascending order, then compare character by character. The optimal approach sorts both strings and checks both possible breaking directions. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - All Permutations	O(n! × n! × n)	O(n! × n)	Generate all permutations of both strings and check every combination
Greedy with Sorting	O(n log n)	O(n)	Sort both strings and check if one can break the other in sorted order

Brute Force - All Permutations — Algorithm Steps

Generate all permutations of s1
Generate all permutations of s2
For each pair of permutations, check if one can break the other
Return true if any valid breaking pair is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements of both strings

Compare All Pairs

Check every permutation pair for breaking condition

Find Match

Return true if any pair satisfies the condition

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void swap(char* a, char* b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

bool canBreak(const char* x, const char* y, int len) {
    for (int i = 0; i < len; i++) {
        if (x[i] < y[i]) return false;
    }
    return true;
}

bool checkPermutations(char* s1, char* s2, int len, int pos1, int pos2) {
    if (pos1 == len && pos2 == len) {
        return canBreak(s1, s2, len) || canBreak(s2, s1, len);
    }
    
    if (pos1 < len) {
        for (int i = pos1; i < len; i++) {
            swap(&s1[pos1], &s1[i]);
            if (checkPermutations(s1, s2, len, pos1 + 1, pos2)) {
                return true;
            }
            swap(&s1[pos1], &s1[i]);
        }
    }
    
    if (pos2 < len) {
        for (int i = pos2; i < len; i++) {
            swap(&s2[pos2], &s2[i]);
            if (checkPermutations(s1, s2, len, pos1, pos2 + 1)) {
                return true;
            }
            swap(&s2[pos2], &s2[i]);
        }
    }
    
    return false;
}

bool solution(char* s1, char* s2) {
    int len = strlen(s1);
    return checkPermutations(s1, s2, len, 0, 0);
}

int main() {
    char s1[1001], s2[1001];
    fgets(s1, sizeof(s1), stdin);
    fgets(s2, sizeof(s2), stdin);
    s1[strcspn(s1, "\n")] = 0;
    s2[strcspn(s2, "\n")] = 0;
    printf(solution(s1, s2) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n! × n)

n! permutations for each string, checking each pair takes O(n)

⚠ Quadratic Growth

Space Complexity

O(n! × n)

Storage for all permutations of both strings

⚠ Quadratic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler