Previous
Coding/Front-end code

Fewest highlighted stretches in an inline line diff

Write codeHard40 min

Your task

A code review page shows a changed line twice, the old version above the new one, and highlights the characters that changed. It leaves as many characters unhighlighted as it can. Among the ways to do that, it picks one with the fewest highlighted stretches, because scattered one-letter highlights are hard to read.

Write fewest_highlights(before, after) that returns the number of highlighted stretches in that best choice.

Input and output:

  • before and after: the old and the new version of the line, each 0 to 300 printable ASCII characters (codes 32 to 126). Characters are compared exactly, so a and A differ.
  • Returns an integer.

Rules:

  • A choice pairs some characters of before with equal characters of after. Pairs keep their order. If position i of before is paired with position j of after, any later paired position of before is paired with a position later than j. No character is in 2 pairs.
  • Every character that is not in a pair is highlighted.
  • A stretch is a run of highlighted characters that sit next to each other in the same line, made as long as it can be.
  • The page only considers choices with the most pairs. Among those, return the smallest total number of stretches in before and after together.

Examples

fewest_highlights(before: str, after: str) -> int
Example 1
Inputfewest_highlights("const color = 'red';", "const colour = 'red';")
Output1
Example 2
Inputfewest_highlights("total = price * qty", "total = price * qty + tax")
Output1
Example 3
Inputfewest_highlights("getUser(id)", "fetchUserById(id)")
Output4