InterviewDB
Experience
Make Word: Minimum Insertions to Form a Target Word from Letters
phone
Interview Experience
Problem
You have a collection of letter tiles (with repetition). Given a target word, determine the minimum number of additional letters you need to purchase (insert) so you can spell the word. Each tile can be used at most once.
python
def min_insertions_to_make_word(tiles: list[str], target: str) -> int:
pass
**Input**: tiles = ['a', 'a', 'b', 'c'], target = "aabbc"
**Output**: 2
# Have: a=2, b=1, c=1. Need: a=2, b=2, c=1.
# Missing: b=1. But also missing one 'b'. Wait: need b=2, have b=1 -> need 1 more b.
# Answer = 1? Check: need a=2 (have 2 ok), b=2 (have 1, need 1 more), c=1 (have 1 ok) -> 1.
# Let's use a cleaner example:
**Input**: tiles = ['a', 'b'], target = "aab"
**Output**: 1
# Have a=1,b=1. Need a=2,b=1. Missing: 1 'a'.
Follow-ups
- What if tiles have costs and you want to minimize total cost, not count of inserted letters?
- How do you handle case-insensitivity?
- Extend: given multiple target words, find the minimum total insertions to spell all of them (tiles are shared).
- What if tiles can be wildcards that match any letter?
Full Details
Problem
You have a collection of letter tiles (with repetition). Given a target word, determine the minimum number of additional letters you need to purchase (insert) so you can spell the word. Each tile can be used at most once.
python
def min_insertions_to_make_word(tiles: list[str], target: str) -> int:
pass
**Input**: tiles = ['a', 'a', 'b', 'c'], target = "aabbc"
**Output**: 2
# Have: a=2, b=1, c=1. Need: a=2, b=2, c=1.
# Missing: b=1. But also missing one 'b'. Wait: need b=2, have b=1 -> need 1 more b.
# Answer = 1? Check: need a=2 (have 2 ok), b=2 (have 1, need 1 more), c=1 (have 1 ok) -> 1.
# Let's use a cleaner example:
**Input**: tiles = ['a', 'b'], target = "aab"
**Output**: 1
# Have a=1,b=1. Need a=2,b=1. Missing: 1 'a'.
Follow-ups
- What if tiles have costs and you want to minimize total cost, not count of inserted letters?
- How do you handle case-insensitivity?
- Extend: given multiple target words, find the minimum total insertions to spell all of them (tiles are shared).
- What if tiles can be wildcards that match any letter?
Free preview. Unlock all Spotify questions →
About This Question
This is a candidate experience report from a spotify interview during the phone round.