題目敘述
題目會給我們兩個字串作為輸入，分別是字串s和字串t，問我最少要做幾次字元轉換，讓字串t和字串s成為Anagram"同字母異序詞"?
註: 例如 god 和 dog 就是 Anagram 同字母異序詞，也是就說，組成字母相同，但是順序可以重新排列。
題目的原文敘述測試範例
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.
把字串t中的一個a改成b，字串s和字串t就是Anagram 同字母異序詞
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.
不用特別調整，原本就是Anagram同字母異序詞
約束條件
Constraints:
1 <= s.length <= 5 * 10^4
字串s的長度介於1~5*10^4之間。
s.length == t.length
字串s的長度 = 字串t的長度。
sandtconsist of lowercase English letters only.
字串s和字串t裡面只會有小寫英文字母。
演算法
其實依照定義出發即可。
這題的目標是讓兩個字串成為Anagram 同字母異序詞，
關鍵就在於，每個曾經出現的英文字母的出現次數必須相同。
到這邊，可以很直覺的聯想到用字典dictionary(或者稱 雜湊映射表Hash table)來實作。
建立兩個字典s_occ_dict，t_occ_dict分別統計兩個字串各自的字母出現次數。
然後，計算出現次數差值的絕對值總和，每做一次字元轉換，就代表有一個舊字元減少出現一次，一個新字元多出現一次，一來一回等於重複計算，最後再除以2，扣掉重複的部分，就是所需字元轉換的次數的最小值。
程式碼
from collections import defaultdict
from string import ascii_lowercase
class Solution:
def minSteps(self, s: str, t: str) -> int:
# dictionary
# key : alphabet letter
# value : occurrence
s_occ_dict = defaultdict( int )
t_occ_dict = defaultdict( int )
# build the dictionary for input string s
for ch in s:
s_occ_dict[ch] += 1
# build the dictionary for input string t
for ch in t:
t_occ_dict[ch] += 1
# counting the minimum distance to anagram
diff = 0
for ch in ascii_lowercase:
diff += abs(s_occ_dict[ch] - t_occ_dict[ch])
return diff//2
關鍵知識點
這題的目標是讓兩個字串成為Anagram 同字母異序詞，
關鍵就在於，每個曾經出現的英文字母的出現次數必須相同。
到這邊，可以很直覺的聯想到用字典dictionary(或者稱 雜湊映射表Hash table)來實作。
複雜度分析
時間複雜度:
從頭到尾掃描過每個字元，所需時間為O(n) = O(字串長度)
空間複雜度:
因為題目已經給了一個很強的條件，字串s和字串t裡面只會有小寫英文字母，所以字典的大小最大就是統計每個小寫字母的出現次數=O(26)=O(1) 常數級別。
Reference:
[1] Minimum Number of Steps to Make Two Strings Anagram - LeetCode
