Merge Strings With Minimum Conflicts
HardDynamic Programming ยท Amazon
Given two lowercase strings a and b, merge them into one string by repeatedly taking the next unused letter from either string, so each string's letters keep their original order.
A conflict is a pair of positions i < j in the merged string where merged[i] > merged[j]. Every such pair counts, including two letters that came from the same input string. Return the minimum number of conflicts over all possible merges.
Example 1
- Input:
- a = "ba", b = "ab"
- Output:
- 1
- Explanation
- Merging as "abab" leaves one conflict, the b at index 1 before the a at index 2.
Example 2
- Input:
- a = "cb", b = "a"
- Output:
- 1
Example 3
- Input:
- a = "", b = "dcba"
- Output:
- 6
- Explanation
- There is only one merge, and every pair of letters is in descending order.
Constraints
0 <= a.length, b.length <= 1000aandbcontain only lowercase English lettersatoz- The answer fits in a 64-bit signed integer