K-Anagrams

mediumSave

CountingHash TableString

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 s1 that need to be changed to make s1 an anagram of s2 is at most k.

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.

Example 1

Input

[
  "\"anagram\"",
  "\"nagaram\"",
  "1"
]

Output

true

Explanation. Both strings are already anagrams, so 0 changes are needed. 0 <= 1 is true.

Example 2

Input

[
  "\"apple\"",
  "\"apply\"",
  "1"
]

Output

true

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.

Example 3

Input

[
  "\"apple\"",
  "\"apples\"",
  "1"
]

Output

false

Explanation. The strings have different lengths (5 vs 6), so they cannot be k-anagrams.

Example 4

Input

[
  "\"foo\"",
  "\"bar\"",
  "1"
]

Output

false

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.

Example 5

Input

[
  "\"abc\"",
  "\"bca\"",
  "0"
]

Output

true

Explanation. The strings 'abc' and 'bca' are already anagrams, so 0 changes are needed. 0 <= 0 is true.

Example 6

Input

[
  "\"abc\"",
  "\"abd\"",
  "0"
]

Output

false

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.

Example 7

Input

[
  "\"abc\"",
  "\"xyz\"",
  "3"
]

Output

true

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.

Example 8

Input

[
  "\"aabbcdefg\"",
  "\"aaabbcdeg\"",
  "1"
]

Output

true

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.

Example 9

Input

[
  "\"football\"",
  "\"baseball\"",
  "2"
]

Output

false

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?

Constraints:

- `1 <= s1.length, s2.length <= 10^5` - `0 <= k <= s1.length` - `s1` and `s2` consist of lowercase English letters only.

Views: 4