Minimum Priority Conflicts When Interleaving Two Lowercase Strings
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
You are given two strings, `primary` (length `m`) and `secondary` (length `n`), made of lowercase English letters. Merge them into one string of length `m + n` that uses every character of both strings and keeps the original relative order of the characters within each string. In other words, the merged string is an interleaving of `primary` and `secondary`.
Letters have priorities: a smaller letter has a higher priority, so `'a'` has the highest priority and `'z'` the lowest. A conflict is a pair of positions in the merged string where a lower-priority letter appears before a higher-priority letter. For example, the merged string `"zab"` has 2 conflicts: `'z'` before `'a'`, and `'z'` before `'b'`.
Return the minimum number of conflicts over all valid merged strings.
### Function Signature
```python
def min_merge_conflicts(primary: str, secondary: str) -> int:
```
### Rules
- The merged string must use every character of `primary` and every character of `secondary` exactly once, and the characters of each input must appear in the same relative order as in that input.
- A conflict is a pair of indices `x < y` in the merged string with `merged[x] > merged[y]` in alphabetical order. Each such pair counts once.
- Two equal letters never form a conflict.
- Conflicts between two characters that come from the same input string count too, even though no merge can change their relative order.
- Return only the minimum count, not the merged string.
### Constraints
- `1 <= m <= 1000` and `1 <= n <= 1000`, where `m = len(primary)` and `n = len(secondary)`
- Both strings contain only the letters `'a'` to `'z'`.
- The answer is at most `(m + n) * (m + n - 1) / 2`, which is below 2,000,000, so it fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: primary = "ca", secondary = "b"
Output: 2
```
The three possible merges are `"bca"` (2 conflicts), `"cba"` (3 conflicts) and `"cab"` (2 conflicts).
**Example 2**
```text
Input: primary = "db", secondary = "ca"
Output: 3
```
The merge `"cadb"` has 3 conflicts (`'c'` before `'a'`, `'c'` before `'b'`, and `'d'` before `'b'`), and no valid merge has fewer.
**Example 3**
```text
Input: primary = "a", secondary = "a"
Output: 0
```
The only merge is `"aa"`, and equal letters do not conflict.
Overview: From an Amazon online assessment: merge two lowercase strings into one while keeping each string's internal order, where smaller letters have higher priority and every lower-priority letter placed before a higher-priority one counts as a conflict. Return the minimum possible number of conflicts over all valid merges.
Read the full Amazon Software Engineer interview experience this question came from
