题目描述

给你两个长度相等的字符串 s 和 t。每一个步骤中，你可以选择将 t 中的 任一字符 替换为 另一个字符。

返回使 t 成为 s 的字母异位词的最小步骤数。

字母异位词 指字母相同，但排列不同的字符串。

样例

输出：s = "bab", t = "aba"
输出：1
提示：用 'b' 替换 t 中的第一个 'a'，t = "bba" 是 s 的一个字母异位词。

输出：s = "leetcode", t = "practice"
输出：5
提示：用合适的字符替换 t 中的 'p', 'r', 'a', 'i' 和 'c'，使 t 变成 s 的字母异位词。

输出：s = "anagram", t = "mangaar"
输出：0
提示："anagram" 和 "mangaar" 本身就是一组字母异位词。 

输出：s = "xxyyzz", t = "xxyyzz"
输出：0

输出：s = "friend", t = "family"
输出：4

限制

• 1 <= s.length <= 50000
• s.length == t.length
• s 和 t 只包含小写英文字母。

算法

(贪心，哈希表) $O(n)$

1. 求出每个单词每种字符的出现次数，并存放在数组中。
2. 每种字符的差值求和，则答案为差值和的一半。
3. 这是因为一次替换操作可以消除两个差值。

时间复杂度

• 扫描两个数组，然后再扫整个字符种类，故时间复杂度为 $O(n)$。

空间复杂度

• 因为字符种类优先，所以仅需要常数的额外空间存放每种字符的个数。

C++ 代码

class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> vs(26, 0), vt(26, 0);

        for (char c : s)
            vs[c - 'a']++;

        for (char c : t)
            vt[c - 'a']++;

        int ans = 0;
        for (int i = 0; i < 26; i++)
            ans += abs(vs[i] - vt[i]);

        return ans / 2;
    }
};