Separate Two Words by Letters

Medium

You are given two strings first and second of lowercase English letters. One edit replaces any letter in either string with any other lowercase letter. You want at least one of these to hold: - every letter of first comes strictly earlier in the alphabet than every letter of second; - every letter of second comes strictly earlier in the alphabet than every letter of first; - both strings consist entirely of one and the same letter. Return the smallest number of edits needed.

Example 1

first="bad", second="fee" → 0

Every letter of first (a, b, d) is already below every letter of second (e, f). No edits are needed.

Example 2

first="zoo", second="pop" → 2

Make second the smaller word: its letters are p, o, p, all below z. Changing both o's in first to z (2 edits) gives "zzz", and every letter of second is now below every letter of first. Nothing cheaper exists, so the answer is 2.

Example 3

first="k", second="k" → 0

Both words already consist of one and the same letter.

Constraints

1 ≤ len(first), len(second) ≤ 10⁵
Both strings contain only lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Counting Prefix Sum

Similar problems

Pieces With Matching Ends Medium Pieces with a Whole Average Weight Medium Matching Ends per Range Medium Pump Rods at Their Peak Hard A Hint for a Digit Guess Medium

Input

first="bad", second="fee"

Expected

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