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.
Overview: 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.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.
Community answers
Answer by ginb
def letters_to_add(original, typed):
# Normalize to lowercase and get character frequencies
# Counter creates a map of char -> frequency
counts = Counter(original.lower())
# Subtract frequencies found in the typed string
for char in typed.lower():
if char in counts:
counts[char] -= 1
# The number of additional letters needed is the sum of
# all positive values remaining in our map.
# We ignore negative values (extra letters in 'typed' that aren't in 'original')
needed = sum(val for val in counts.values() if val > 0)
return needed