Skip to main content

Fewest Deletions for Matching Anagram

medium
StringHash TableCountingHashmap Lookup
Asked atAmazonMicrosoftAdobe

Problem Description

You are given two strings `source` and `target`. In one operation you may delete any single character from either string. Return the minimum total number of deletions required to make `source` and `target` **anagrams** of each other (i.e. they contain exactly the same multiset of characters).

Characters that remain in both strings after deletions must match in frequency.

**Example 1:**
```
Input: source = "kindly", target = "killing"
Output: 4
Explanation: Keep 'k','i','l' in each (3 characters each).
source deletions: 'n','d','y' (3 deletions)
target deletions: second 'l','i','n','g' — wait, target "killing" keeps k,i,l,l,i,n,g.
Actually keep common: k(1),i(1),l(1) → delete 'n','d','y' from source (3) and delete 'l','i','n','g' from target (4) → total 7?
Re-examine: freq(source)={k:1,i:1,n:1,d:1,l:1,y:1}, freq(target)={k:1,i:2,l:2,n:1,g:1}.
Overlap per char: k→1,i→1,l→1,n→1 = 4 kept. source has 6 chars, target has 7 chars. Deletions = (6-4)+(7-4) = 2+3 = 5.
Output: 5
```

**Example 2:**
```
Input: source = "broom", target = "motor"
Output: 4
Explanation: freq(source)={b:1,r:1,o:2,m:1}, freq(target)={m:1,o:1,t:1,r:1}.
Overlap: m→1,o→1,r→1 = 3 kept. Deletions = (5-3)+(5-3) = 4.
```

Constraints

  • 1 <= source.length, target.length <= 100000
  • source and target consist of lowercase English letters only

Follow-up

What if the alphabet is arbitrary Unicode (not just lowercase letters)? How does the space complexity change?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.