Katkat
Back

Minimum Priority Conflicts When Interleaving Two Lowercase Strings

AmazonSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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

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

Input: primary = "ca", secondary = "b"
Output: 2

The three possible merges are "bca" (2 conflicts), "cba" (3 conflicts) and "cab" (2 conflicts).

Example 2

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

Input: primary = "a", secondary = "a"
Output: 0

The only merge is "aa", and equal letters do not conflict.