K-Anagrams
Given two strings s1 and s2, and an integer k, determine if s1 and s2 are k-anagrams.
Two strings are considered k-anagrams if:
- They have the same length.
- The number of characters in
s1that need to be changed to makes1an anagram ofs2is at mostk.
An anagram means that the two strings contain the same characters with the same frequencies, just possibly in a different order. For example, "listen" and "silent" are anagrams.
You need to find the minimum number of characters you would need to change in s1 to transform it into s2's character composition. If this minimum number is less than or equal to k, return true; otherwise, return false.
[ "\"anagram\"", "\"nagaram\"", "1" ]
Explanation. Both strings are already anagrams, so 0 changes are needed. 0 <= 1 is true.
[ "\"apple\"", "\"apply\"", "1" ]
Explanation. To transform 'apple' into an anagram of 'apply', one character 'e' needs to be changed to 'y'. This requires 1 change. 1 <= 1 is true.
[ "\"apple\"", "\"apples\"", "1" ]
Explanation. The strings have different lengths (5 vs 6), so they cannot be k-anagrams.
[ "\"foo\"", "\"bar\"", "1" ]
Explanation. Freq('foo'): {f:1, o:2}. Freq('bar'): {b:1, a:1, r:1}. To transform 'foo' into an anagram of 'bar', 'f' must change, and both 'o's must change. This requires 3 changes. 3 <= 1 is false.
[ "\"abc\"", "\"bca\"", "0" ]
Explanation. The strings 'abc' and 'bca' are already anagrams, so 0 changes are needed. 0 <= 0 is true.
[ "\"abc\"", "\"abd\"", "0" ]
Explanation. Freq('abc'): {a:1, b:1, c:1}. Freq('abd'): {a:1, b:1, d:1}. To transform 'abc' into an anagram of 'abd', 'c' needs to be changed to 'd'. This requires 1 change. 1 <= 0 is false.
[ "\"abc\"", "\"xyz\"", "3" ]
Explanation. Freq('abc'): {a:1, b:1, c:1}. Freq('xyz'): {x:1, y:1, z:1}. All three characters in 'abc' need to be changed ('a'->'x', 'b'->'y', 'c'->'z'). This requires 3 changes. 3 <= 3 is true.
[ "\"aabbcdefg\"", "\"aaabbcdeg\"", "1" ]
Explanation. Freq('aabbcdefg'): {a:2, b:2, c:1, d:1, e:1, f:1, g:1}. Freq('aaabbcdeg'): {a:3, b:2, c:1, d:1, e:1, g:1}. Only 'f' in s1 needs to be changed to an 'a' (to match the third 'a' in s2). This is 1 change. 1 <= 1 is true.
[ "\"football\"", "\"baseball\"", "2" ]
Explanation. Freq('football'): {f:1, o:2, t:1, b:1, a:1, l:2}. Freq('baseball'): {b:2, a:2, s:2, e:1, l:1}. Characters that need to be changed in s1: 'f', both 'o's, 't', and one 'l'. This sums up to 1+2+1+1 = 5 changes. 5 <= 2 is false.
Follow-up: Can you solve this problem if the strings can contain Unicode characters? How would your approach change to handle a larger character set efficiently?
- `1 <= s1.length, s2.length <= 10^5` - `0 <= k <= s1.length` - `s1` and `s2` consist of lowercase English letters only.
- Views
- 11