[LeetCode] 1347. Minimum Number of Steps to Make Two Strings Anagram #1347

grandyang · 2019-05-30T16:35:01Z

You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.

Return the minimum number of steps to make t an anagram of s.

An Anagram 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 and t 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/