Medium

Quiz

#1433 Check If a String Can Break Another String

APPROACH

You are given two equal-length strings s1 and s2. Determine whether there exists a rearrangement of s1 that dominates some rearrangement of s2, or vice versa.

A string x of length n dominates string y of the same length when x[i] >= y[i] alphabetically for every index i from 0 to 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

1 of 4

1:00

What is the optimal approach for this problem?