[LeetCode] 1347. Minimum Number of Steps to Make Two Strings Anagram 制造字母異位詞的最小步驟數(shù)

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是變位詞。所謂的變位詞，就是兩個單詞中字符的種類和個數(shù)均相同，就是字符的順序不同而已。之前的題目中也做過不少關(guān)于變位詞的題目，比如 Valid Anagram，Group Anagrams，Find Anagram Mappings，Find All Anagrams in a String 等等。這類題目的核心就是統(tǒng)計字符的出現(xiàn)次數(shù)，這道題也不例外，這里使用一個 HashMap 來統(tǒng)計字符串s中每個字符的出現(xiàn)次數(shù)。然后遍歷字符串t，對于每個遍歷到的字符，將 HashMap 中該字符的映射值自減1，這樣操作之后映射值就可正可負(fù)，還可能為0。當(dāng)某個映射值為正數(shù)的時候，則說明該字符在s中的數(shù)量多，若為負(fù)數(shù)，則說明該字符在t中的數(shù)量多，若為0，則說明該字符在s和t中的個數(shù)一樣多。由于字符串s和t的長度相同，則正數(shù)的映射值累加和一定等于負(fù)數(shù)映射值的累加和，而且只要將所有的正數(shù)的映射字符替換成負(fù)數(shù)的映射字符，則s和t就會變成變位詞，且替換次數(shù)最少，參見代碼如下：

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 同步地址:

https://github.com/grandyang/leetcode/issues/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/