1347 Minimum Number of Steps to Make Two Strings Anagram 制造字母異位詞的最小步驟數
Description:
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:
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 * 10^4
s.length == t.length
s and t consist of lowercase English letters only.
題目描述：
給你兩個長度相等的字符串 s 和 t。每一個步驟中妒挎，你可以選擇將 t 中的 任一字符 替換為 另一個字符腿短。
返回使 t 成為 s 的字母異位詞的最小步驟數。
字母異位詞 指字母相同，但排列不同（也可能相同）的字符串。
示例：
示例 1：
輸出：s = "bab", t = "aba"
輸出：1
提示：用 'b' 替換 t 中的第一個 'a'，t = "bba" 是 s 的一個字母異位詞俗孝。
示例 2：
輸出：s = "leetcode", t = "practice"
輸出：5
提示：用合適的字符替換 t 中的 'p', 'r', 'a', 'i' 和 'c'，使 t 變成 s 的字母異位詞魄健。
示例 3：
輸出：s = "anagram", t = "mangaar"
輸出：0
提示："anagram" 和 "mangaar" 本身就是一組字母異位詞赋铝。
示例 4：
輸出：s = "xxyyzz", t = "xxyyzz"
輸出：0
示例 5：
輸出：s = "friend", t = "family"
輸出：4
提示：
1 <= s.length <= 50000
s.length == t.length
s 和 t 只包含小寫英文字母
思路：
模擬
統(tǒng)計 s 和 t 的不同字符的個數
只需要看 s 比 t 多的字符, 這個數量實際上也是 t 比 s 少的字符
時間復雜度為 O(n), 空間復雜度為 O(1)
代碼:
C++:
class Solution
{
public:
int minSteps(string s, string t)
{
vector<int> count(26);
int result = 0, n = s.size();
for (int i = 0; i < n; i++)
{
++count[s[i] - 'a'];
--count[t[i] - 'a'];
}
for (const auto& i : count) result += max(0, i);
return result;
}
};
Java:
class Solution {
public int minSteps(String s, String t) {
int count[] = new int[26], result = 0, n = s.length();
for (int i = 0; i < n; i++) {
++count[s.charAt(i) - 'a'];
--count[t.charAt(i) - 'a'];
}
for (int i : count) result += Math.max(0, i);
return result;
}
}
Python:
class Solution:
def minSteps(self, s: str, t: str) -> int:
return len(list((Counter(s) - Counter(t)).elements()))
