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.