1433. Check If a String Can Break Another String Solution

The problem

Given two strings: s1 and s2 with the same size, check if some permutation of string s1 can break some permutation of string s2 or vice-versa. In other words s2 can break s1 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.

Example 1:

Input: s1 = "abc", s2 = "xya"
Output: true
Explanation: "ayx" is a permutation of s2="xya" which can break to string "abc" which is a permutation of s1="abc".

Example 2:

Input: s1 = "abe", s2 = "acd"
Output: false 
Explanation: All permutations for s1="abe" are: "abe", "aeb", "bae", "bea", "eab" and "eba" and all permutation for s2="acd" are: "acd", "adc", "cad", "cda", "dac" and "dca". However, there is not any permutation from s1 which can break some permutation from s2 and vice-versa.

Example 3:

Input: s1 = "leetcodee", s2 = "interview"
Output: true

Constraints:

s1.length == n
s2.length == n
1 <= n <= 10^5
All strings consist of lowercase English letters.

Approach overview

Problem Overview: You are given two strings of equal length. A string s1 can break s2 if after permuting both strings, every character in s1 is greater than or equal to the corresponding character in s2. The task is to determine whether either string can break the other.

Approach 1: Sorting and Comparison Approach (O(n log n) time, O(1) or O(n) space)

The key observation: if a valid permutation exists, sorting both strings gives the most favorable comparison order. Convert both strings to arrays, sort them, then compare characters index by index. If s1[i] >= s2[i] for all i, then s1 can break s2. Perform the symmetric check as well to see if s2 can break s1. Sorting ensures characters are aligned in increasing order so the greedy comparison works. This approach relies on sorting plus a simple linear scan. Time complexity is O(n log n) due to sorting, and space is O(1) if sorting in place or O(n) depending on language implementation.

Approach 2: Counting Frequency Approach (O(n) time, O(1) space)

Since characters are limited to lowercase English letters, sorting can be replaced with counting frequencies. Build two frequency arrays of size 26 for both strings. Then simulate the sorted comparison by walking from 'a' to 'z', maintaining prefix sums that represent how many characters have appeared so far. Track whether the cumulative count of one string ever becomes smaller than the other during comparison. If the ordering constraint holds for all characters, that string can break the other. This technique avoids explicit sorting and uses a greedy prefix comparison over character counts. Time complexity becomes O(n + 26) which simplifies to O(n), and space is O(1). The logic combines ideas from string processing and greedy ordering.

Recommended for interviews: The sorting approach is the most commonly expected answer. It is easy to reason about and communicates the core insight quickly: align both strings in sorted order and check dominance character by character. Mentioning the frequency-count optimization shows deeper understanding and demonstrates how to reduce the O(n log n) sorting step to O(n) using fixed alphabet constraints.

Approach 1: Sorting and Comparison Approach

In this approach, the key idea is that by sorting both strings, you can easily determine if one can break the other by simply comparing them position by position. The sorted order ensures that if one element in s1_sorted is greater than or equal to the corresponding element in s2_sorted, then any permutation of s1 can be mapped to a permutation of s2.

To implement this, follow these steps:

Sort both strings s1 and s2.
Check if s1_sorted can break s2_sorted by verifying if each character in s1_sorted[i] is greater than or equal to s2_sorted[i].
Similarly, check if s2_sorted can break s1_sorted.
If either condition holds true, return true; otherwise, return false.

Python

def canBreak(s1, s2):
    s1_sorted = sorted(s1)
    s2_sorted = sorted(s2)

    s1_can_break_s2 = all(s1_sorted[i] >= s2_sorted[i] for i in range(len(s1)))
    s2_can_break_s1 = all(s2_sorted[i] >= s1_sorted[i] for i in range(len(s1)))

    return s1_can_break_s2 or s2_can_break_s1

s1 = "leetcodee"
s2 = "interview"
print(canBreak(s1, s2))

Java

import java.util.Arrays;

public class Main {
    public static boolean canBreak(String s1, String s2) {
        char[] s1Array = s1.toCharArray();
        char[] s2Array = s2.toCharArray();
        Arrays.sort(s1Array);
        Arrays.sort(s2Array);

        boolean s1CanBreakS2 = true;
        boolean s2CanBreakS1 = true;

        for (int i = 0; i < s1Array.length; i++) {
            if (s1Array[i] < s2Array[i]) s1CanBreakS2 = false;
            if (s2Array[i] < s1Array[i]) s2CanBreakS1 = false;
        }

        return s1CanBreakS2 || s2CanBreakS1;
    }

    public static void main(String[] args) {
        String s1 = "leetcodee";
        String s2 = "interview";
        System.out.println(canBreak(s1, s2));
    }
}

C++

#include <iostream>
#include <algorithm>
using namespace std;

bool canBreak(string s1, string s2) {
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());

    bool s1CanBreakS2 = true;
    bool s2CanBreakS1 = true;

    for (int i = 0; i < s1.length(); ++i) {
        if (s1[i] < s2[i]) s1CanBreakS2 = false;
        if (s2[i] < s1[i]) s2CanBreakS1 = false;
    }

    return s1CanBreakS2 || s2CanBreakS1;
}

int main() {
    string s1 = "leetcodee", s2 = "interview";
    cout << (canBreak(s1, s2) ? "true" : "false") << endl;
    return 0;
}

JavaScript

function canBreak(s1, s2) {
    let s1Sorted = s1.split('').sort();
    let s2Sorted = s2.split('').sort();

    let s1CanBreakS2 = true;
    let s2CanBreakS1 = true;

    for (let i = 0; i < s1.length; i++) {
        if (s1Sorted[i] < s2Sorted[i]) s1CanBreakS2 = false;
        if (s2Sorted[i] < s1Sorted[i]) s2CanBreakS1 = false;
    }

    return s1CanBreakS2 || s2CanBreakS1;
}

const s1 = "leetcodee";
const s2 = "interview";
console.log(canBreak(s1, s2));

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

int compare(const void* a, const void* b) {
    return (*(char*)a - *(char*)b);
}

bool canBreak(char* s1, char* s2) {
    int n = strlen(s1);
    qsort(s1, n, sizeof(char), compare);
    qsort(s2, n, sizeof(char), compare);

    bool s1CanBreakS2 = true;
    bool s2CanBreakS1 = true;

    for (int i = 0; i < n; ++i) {
        if (s1[i] < s2[i]) s1CanBreakS2 = false;
        if (s2[i] < s1[i]) s2CanBreakS1 = false;
    }

    return s1CanBreakS2 || s2CanBreakS1;
}

int main() {
    char s1[] = "leetcodee";
    char s2[] = "interview";
    printf("%s\n", canBreak(s1, s2) ? "true" : "false");
    return 0;
}

using System;

class Program {
    static bool CanBreak(string s1, string s2) {
        char[] s1Arr = s1.ToCharArray();
        char[] s2Arr = s2.ToCharArray();
        Array.Sort(s1Arr);
        Array.Sort(s2Arr);

        bool s1CanBreakS2 = true;
        bool s2CanBreakS1 = true;

        for (int i = 0; i < s1Arr.Length; i++) {
            if (s1Arr[i] < s2Arr[i]) s1CanBreakS2 = false;
            if (s2Arr[i] < s1Arr[i]) s2CanBreakS1 = false;
        }

        return s1CanBreakS2 || s2CanBreakS1;
    }

    static void Main(string[] args) {
        string s1 = "leetcodee";
        string s2 = "interview";
        Console.WriteLine(CanBreak(s1, s2));
    }
}

The Python solution sorts both strings and uses list comprehension combined with all() to check the breaking condition efficiently.

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for the sorted lists.

Try this approach in the editor

Approach 2: Counting Frequency Approach

This approach takes advantage of counting the frequency of each character in both strings. By using arrays to count the occurrences of each character (since there are only 26 lowercase English letters), you can directly compare these arrays to determine if one string can break the other.

The steps are as follows:

Create frequency arrays for both strings with a length of 26 (one for each letter of the alphabet).
Fill these arrays with the count of each character in the respective strings.
Compare the cumulative frequency counts to see if one string's count consistently exceeds or equals the other's.
If either string can break the other, return true; otherwise, return false.

Python

def canBreak(s1, s2):
    freq1 = [0] * 26
    freq2 = [0] * 26

    for c in s1:
        freq1[ord(c) - ord('a')] += 1
    for c in s2:
        freq2[ord(c) - ord('a')] += 1

    s1_can_break_s2 = True
    s2_can_break_s1 = True

    sum1 = sum2 = 0
    for i in range(26):
        sum1 += freq1[i]
        sum2 += freq2[i]
        if sum1 < sum2:
            s1_can_break_s2 = False
        if sum2 < sum1:
            s2_can_break_s1 = False

    return s1_can_break_s2 or s2_can_break_s1

s1 = "leetcodee"
s2 = "interview"
print(canBreak(s1, s2))

Java

public class Main {
    public static boolean canBreak(String s1, String s2) {
        int[] freq1 = new int[26];
        int[] freq2 = new int[26];

        for (char c : s1.toCharArray()) freq1[c - 'a']++;
        for (char c : s2.toCharArray()) freq2[c - 'a']++;

        boolean s1CanBreakS2 = true, s2CanBreakS1 = true;
        int sum1 = 0, sum2 = 0;

        for (int i = 0; i < 26; i++) {
            sum1 += freq1[i];
            sum2 += freq2[i];
            if (sum1 < sum2) s1CanBreakS2 = false;
            if (sum2 < sum1) s2CanBreakS1 = false;
        }

        return s1CanBreakS2 || s2CanBreakS1;
    }

    public static void main(String[] args) {
        String s1 = "leetcodee";
        String s2 = "interview";
        System.out.println(canBreak(s1, s2));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

bool canBreak(const string& s1, const string& s2) {
    vector<int> freq1(26, 0), freq2(26, 0);

    for (char c : s1) freq1[c - 'a']++;
    for (char c : s2) freq2[c - 'a']++;

    bool s1CanBreakS2 = true, s2CanBreakS1 = true;
    int sum1 = 0, sum2 = 0;

    for (int i = 0; i < 26; ++i) {
        sum1 += freq1[i];
        sum2 += freq2[i];
        if (sum1 < sum2) s1CanBreakS2 = false;
        if (sum2 < sum1) s2CanBreakS1 = false;
    }

    return s1CanBreakS2 || s2CanBreakS1;
}

int main() {
    string s1 = "leetcodee", s2 = "interview";
    cout << (canBreak(s1, s2) ? "true" : "false") << endl;
    return 0;
}

JavaScript

function canBreak(s1, s2) {
    let freq1 = new Array(26).fill(0);
    let freq2 = new Array(26).fill(0);

    for (let c of s1) freq1[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    for (let c of s2) freq2[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;

    let s1CanBreakS2 = true;
    let s2CanBreakS1 = true;
    let sum1 = 0, sum2 = 0;

    for (let i = 0; i < 26; i++) {
        sum1 += freq1[i];
        sum2 += freq2[i];
        if (sum1 < sum2) s1CanBreakS2 = false;
        if (sum2 < sum1) s2CanBreakS1 = false;
    }

    return s1CanBreakS2 || s2CanBreakS1;
}

const s1 = "leetcodee";
const s2 = "interview";
console.log(canBreak(s1, s2));

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

bool canBreak(char* s1, char* s2) {
    int freq1[26] = {0}, freq2[26] = {0};
    int n = strlen(s1);

    for (int i = 0; i < n; ++i) {
        freq1[s1[i] - 'a']++;
        freq2[s2[i] - 'a']++;
    }

    bool s1CanBreakS2 = true, s2CanBreakS1 = true;
    int sum1 = 0, sum2 = 0;

    for (int i = 0; i < 26; ++i) {
        sum1 += freq1[i];
        sum2 += freq2[i];
        if (sum1 < sum2) s1CanBreakS2 = false;
        if (sum2 < sum1) s2CanBreakS1 = false;
    }
    return s1CanBreakS2 || s2CanBreakS1;
}

int main() {
    char s1[] = "leetcodee";
    char s2[] = "interview";
    printf("%s\n", canBreak(s1, s2) ? "true" : "false");
    return 0;
}

using System;

class Program {
    static bool CanBreak(string s1, string s2) {
        int[] freq1 = new int[26];
        int[] freq2 = new int[26];

        foreach (char c in s1) freq1[c - 'a']++;
        foreach (char c in s2) freq2[c - 'a']++;

        bool s1CanBreakS2 = true, s2CanBreakS1 = true;
        int sum1 = 0, sum2 = 0;

        for (int i = 0; i < 26; i++) {
            sum1 += freq1[i];
            sum2 += freq2[i];
            if (sum1 < sum2) s1CanBreakS2 = false;
            if (sum2 < sum1) s2CanBreakS1 = false;
        }

        return s1CanBreakS2 || s2CanBreakS1;
    }

    static void Main(string[] args) {
        string s1 = "leetcodee";
        string s2 = "interview";
        Console.WriteLine(CanBreak(s1, s2));
    }
}

The Python solution builds frequency lists for both strings and checks cumulative frequencies to decide if a break is possible between permutations.

Complexity

Time Complexity: O(n).
Space Complexity: O(1) with constant space for frequency arrays.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function checkIfCanBreak(s1: string, s2: string): boolean {
    const cs1: string[] = Array.from(s1);
    const cs2: string[] = Array.from(s2);
    cs1.sort();
    cs2.sort();
    const check = (cs1: string[], cs2: string[]) => {
        for (let i = 0; i < cs1.length; i++) {
            if (cs1[i] < cs2[i]) {
                return false;
            }
        }
        return true;
    };
    return check(cs1, cs2) || check(cs2, cs1);
}

func checkIfCanBreak(s1 string, s2 string) bool {
	cs1 := []byte(s1)
	cs2 := []byte(s2)
	sort.Slice(cs1, func(i, j int) bool { return cs1[i] < cs1[j] })
	sort.Slice(cs2, func(i, j int) bool { return cs2[i] < cs2[j] })
	check := func(cs1, cs2 []byte) bool {
		for i := range cs1 {
			if cs1[i] < cs2[i] {
				return false
			}
		}
		return true
	}
	return check(cs1, cs2) || check(cs2, cs1)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sorting and Comparison Approach	Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for the sorted lists.
Counting Frequency Approach	Time Complexity: O(n). Space Complexity: O(1) with constant space for frequency arrays.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Sorting and Comparison	O(n log n)	O(1) / O(n)	Best general solution; easiest to implement and explain during interviews
Counting Frequency	O(n)	O(1)	When alphabet size is fixed (e.g., lowercase letters) and you want to avoid sorting

Frequently asked questions

Is Check If a String Can Break Another String easy or hard?

The problem is rated Medium because the key insight is recognizing that sorting both strings reveals whether a valid permutation exists. Once that idea is understood, the implementation becomes straightforward. The frequency-count optimization adds a small extra layer of algorithmic thinking.

Check If a String Can Break Another String Python/Java solution

In Python or Java, the simplest implementation converts each string to a character array, sorts them, and checks pairwise comparisons in a loop. If all characters in one sorted string are greater than or equal to the other, return true. The same logic works in C++, JavaScript, and C# with identical O(n log n) complexity.

How to solve Check If a String Can Break Another String in O(n)?

Use two frequency arrays of size 26 to count characters in both strings. Iterate from 'a' to 'z' while maintaining cumulative counts that simulate the sorted order. If the cumulative count of one string never falls behind the other, that string can break the other. This avoids sorting and reduces time complexity to O(n) with O(1) space.

What is the best approach for Check If a String Can Break Another String?

The most common solution sorts both strings and compares them character by character. After sorting, check whether s1[i] >= s2[i] for every index or vice versa. This greedy comparison works because sorting places characters in the best possible order. The approach runs in O(n log n) time with O(1) or O(n) extra space depending on the language.

Is Check If a String Can Break Another String asked at Google/Amazon/Meta?

Problems involving string ordering, greedy comparisons, and frequency counting commonly appear in interviews at companies like Amazon, Google, and Meta. Variants often test whether one sequence dominates another after reordering. The question evaluates understanding of sorting strategies and prefix comparisons.

What data structure is used in Check If a String Can Break Another String?

The core solutions use arrays and basic string manipulation. The sorting approach relies on sorted arrays of characters, while the optimized method uses fixed-size frequency arrays of length 26. Both approaches iterate linearly through the characters to verify the dominance condition.

What is the time complexity of Check If a String Can Break Another String?

The typical sorting solution runs in O(n log n) time because both strings must be sorted before comparison. After sorting, a single O(n) pass verifies whether one string dominates the other. With a frequency counting optimization, the problem can be solved in O(n) time using a fixed 26-character alphabet.

Check If a String Can Break Another String solution and explanation

The problem

Approach overview

Approach 1: Sorting and Comparison Approach

Approach 2: Counting Frequency Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Check If a String Can Break Another String solution and explanation

The problem

Approach overview

Approach 1: Sorting and Comparison Approach

Approach 2: Counting Frequency Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems