One Word Outranks the Other

Medium

You are given two words first and second of equal length, made of lowercase English letters. Say that word x *outranks* word y if at every position i the letter x[i] comes no earlier in the alphabet than y[i] (equal letters are fine). You may rearrange the letters inside each word however you like. Return True if some rearrangement makes one of the words (either one) outrank the other, and False otherwise.

Example 1

first="cat", second="dog" → False

Sort both: "act" and "dgo". a ≤ d and c ≤ g, but t > o, so neither word can beat the other in every position.

Example 2

first="bee", second="ace" → True

Sorted they are "bee" and "ace": b ≥ a, e ≥ c, e ≥ e, so first outranks second.

Example 3

first="zz", second="zz" → True

Constraints

1 ≤ len(first) = len(second) ≤ 10⁵
Both words consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String Sorting

Similar problems

Biggest Number From Pieces Medium No Twin Letters Side by Side Medium Round Prices to a Total Medium Distinct Letter Counts Medium Nine-Button Layout Medium

Input

first="cat", second="dog"

Expected

False

Run checks the first 3 tests in your browser. Submit checks all 97 tests on the server, hidden ones included.