You are given two strings of the same lengths andt. In one step you can chooseany character oft and replace it withanother character.

Returnthe minimum number of steps to maket an anagram ofs.

AnAnagram of a string is a string that contains the same characters with a different (or the same) ordering.

Example 1:

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

Example 2:

Input: s = "leetcode", t = "practice"
Output: 5
Explanation: Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s.

Example 3:

Input: s = "anagram", t = "mangaar"
Output: 0
Explanation: "anagram" and "mangaar" are anagrams.

Constraints:

• 1 <= s.length <= 5 * 104
• s.length == t.length
• s andt consist of lowercase English letters only.

这道题给了两个字符串s和t，说是可以替换t中的字符，问最少替换多少个字符可以使得其与s是变位词。所谓的变位词，就是两个单词中字符的种类和个数均相同，就是字符的顺序不同而已。之前的题目中也做过不少关于变位词的题目，比如Valid Anagram，Group Anagrams，Find Anagram Mappings，Find All Anagrams in a String 等等。这类题目的核心就是统计字符的出现次数，这道题也不例外，这里使用一个 HashMap 来统计字符串s中每个字符的出现次数。然后遍历字符串t，对于每个遍历到的字符，将 HashMap 中该字符的映射值自减1，这样操作之后映射值就可正可负，还可能为0。当某个映射值为正数的时候，则说明该字符在s中的数量多，若为负数，则说明该字符在t中的数量多，若为0，则说明该字符在s和t中的个数一样多。由于字符串s和t的长度相同，则正数的映射值累加和一定等于负数映射值的累加和，而且只要将所有的正数的映射字符替换成负数的映射字符，则s和t就会变成变位词，且替换次数最少，参见代码如下：

class Solution {public:    int minSteps(string s, string t) {        int res = 0;        unordered_map<char, int> charCnt;        for (char c : s) ++charCnt[c];        for (char c : t) --charCnt[c];        for (auto a : charCnt) {            if (a.second > 0) res += abs(a.second);        }        return res;    }};

Github 同步地址:

#1347

类似题目：

Valid Anagram

Group Anagrams

Find Anagram Mappings

Find All Anagrams in a String

Determine if Two Strings Are Close

Minimum Number of Steps to Make Two Strings Anagram II

参考资料：

https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/

https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/solutions/503460/java-maintain-an-array-to-record-the-occurrence-of-characters/

https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/solutions/503450/java-python-3-count-occurrences-and-sum-the-difference-w-analysis/

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏

---|---