Coding questions · Meta

Compute missing letters to form original string

This question evaluates string-processing skills, the ability to count character multiplicities case-insensitively, and understanding of algorithmic time-complexity.

Implement a function that, given two strings original and typed (typed is a misspelled/partial version of original), returns the number of additional letters that must be added to typed so that some rearrangement of typed equals original. Treat letters case-insensitively and count multiplicities. Examples: original = "Fiction", typed = "fin" -> 4; original = "reference", typed = "fence" -> 4. Aim for O(n) time using a character-frequency map.

Missing Letters To Form Original

Return how many additional letters must be added to typed so its letters can be rearranged to cover original, case-insensitively.

Examples

Example 1

Input: ('Fiction','fin')
Output: 4

Explanation: Missing c,t,i,o.

Example 2

Input: ('reference','fence')
Output: 4

Explanation: Missing two r letters and two e letters.

Hints

Clarify edge cases before coding.
Keep the return value deterministic.