Fewest Deletions for Matching Anagram
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.