Skip to main content
Talentd

Check If a String Can Break Another String - Solution & Explanation

MediumStringGreedySorting17 min read
Practice this problem

Problem Statement

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.

The C solution sorts both strings using qsort and then compares the characters at each position. Two boolean variables track whether s1 can break s2 or vice versa.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in-place.

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.

The C solution counts character occurrences in frequency arrays for both strings and compares cumulative sums to decide if one can break the other.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + 26) = O(n) for counting and comparing.
Space Complexity: O(1) due to fixed-size frequency arrays.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Comparison Approach

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in-place.

Counting Frequency Approach

Time Complexity: O(n + 26) = O(n) for counting and comparing.
Space Complexity: O(1) due to fixed-size frequency arrays.

Default Approach—

Detailed Complexity Analysis

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

Video Solution

1433. Check If a String Can Break Another String || using C++ || Leetcode problem || Greedy Topic • Cogent Coder • 619 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Check If a String Can Break Another String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring