Compute missing letters to form original string
Company: Meta
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
Quick Answer: This question evaluates string-processing skills, the ability to count character multiplicities case-insensitively, and understanding of algorithmic time-complexity.
Return how many additional letters must be added to typed so its letters can be rearranged to cover original, case-insensitively.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('Fiction','fin')
Expected Output: 4
Explanation: Missing c,t,i,o.
Input: ('reference','fence')
Expected Output: 4
Explanation: Missing two r letters and two e letters.
Input: ('AaBb','bbaa')
Expected Output: 0
Explanation: Case-insensitive counts already match.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.