FastPrepFastPrep
Problem Brief

Minimum Merge Conflicts

INTERNOA
See Amazon online assessment and hiring insights

Developers want to merge two source-control branches into one unified branch while preserving the relative order of commits from each branch.

Each branch is represented by a lowercase string. Each character represents a commit priority, where a lower alphabetical character has higher priority.

A conflict occurs when, in the merged branch, a lower-priority commit appears before a higher-priority commit. In other words, for positions i < j in the merged string, there is a conflict when merged[i] > merged[j].

Return the minimum possible number of conflicts over all valid merges of primary and secondary.

A valid merge must contain every character from both branches and preserve the original order within each input branch.

1Example 1

Input
primary = "zc", secondary = "d"
Output
2
Explanation

Valid merges include zcd, zdc, and dzc. Their conflict counts are 2, 3, and 2, so the minimum is 2.

2Example 2

Input
primary = "dae", secondary = "add"
Output
1
Explanation

One optimal merge is adddae. The only conflict is d appearing before a inside the original primary branch, which cannot be avoided.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= primary.length, secondary.length <= 1000
  • primary and secondary contain lowercase English letters only.
public int getMinimumConflicts(String primary, String secondary) {
    // write your code here
}
Input

primary

"zc"

secondary

"d"

Output

2

Sign in to submit your solution.