主題
題目連結：
題目意譯：
你被給定一字串 s，其由小寫英文字母組成。
在一步之中，你可以選擇 s 中任何兩個相鄰的字元並將兩者交換。
回傳把 s 變成一個迴文最少所需步驟。
注意到輸入測資之生成滿足 s 必定可以被轉變成一個迴文。
限制：
1 ≦ s.length ≦ 2000
s 只由小寫英文字母組成。
s 可以藉由有限步驟來轉變成一個迴文字串。
範例測資：
範例 1：
輸入： s = "aabb"
輸出： 2
解釋：
我們可以從 s 中獲得兩個迴文，即 "abba" 和 "baab"。
- 我們可以在兩步之內從 s 得到 "abba"："aabb" → "abab" → "abba"。
- 我們可以在兩步之內從 s 得到 "baab"："aabb" → "abab" → "baab"。
因此把 s 變成一個迴文最少所需步驟為 2 步。
範例 2：
輸入： s = "letelt"
輸出： 2
解釋：
我們可以在兩步內從 s 中得到的其中一個迴文為 "lettel"。
其中一個可以得到該迴文的方式為 "letelt" → "letetl" → "lettel"。
其他迴文如 "tleelt" 也可以在兩步內得到。
可以證明不可能可以在少於兩步以內得到一個迴文。
解題思維：
首先我們可以觀察到如果有一種字母出現超過 2 次，例如說 s = "mcmcbbcdddd" 中的 c 和 d。則將存在一種最佳交換步驟（最佳解）使得最左邊和最右邊的該種字元會「配對」在一起（即互相對稱），如前例的
"mcmcbbcdddd"
中最左側的 c 與最右側的 c 將配在一起（以紅色表示）、最左側的 d 與最右側的 d 將配在一起（以藍色表示）。
原因很簡單，因為其他任何一種會使得最左側的該種字母（或最右側）與其他位置的相同字母配對的方式必定會跨過最右側的該種字元（或最左側），而我們可以單純地換成最右側（或最左側）繼續交換到對應的位置即可。
同理，從左數過來第二個字元將會與從右數過來第二個的相同字母配對，以此類推。
當然，如果該字母出現奇數次，則代表迴文的中心必為該種字母。所以該種字母從最外層兩兩配對完後剩下的那唯一一個字母將會一路交換位置到迴文中心。
接著我們可以觀察到會存在一種最佳解，使得當前字串中與開頭字母（或結尾字母）對應（根據上面的觀察）的字母一路交換到結尾（或開頭）。
承上例，"mcmcbbcdddd" 會存在一種最佳解會使得右側的 m 一路交換到結尾變成
"mccbbcddddm"
同時也存在一種最佳解是使得 "mcmcbbcdddd" 最左側的 d 一路交換到開頭，得到
"dmcmcbbcddd"
原因也一樣很單純，以上例說明，如果 "mcmcbbcdddd" 改成是開頭的 m 移動到對應的位置，如
"cmcbbcdddmd"
首先所需步數會變多，而且之後要配對其他字母時必定會存在字母會跨過這兩個 m 中的其中一者（如果沒有則代表這兩個 m 配完之後整個字串就變成迴文了）。就這兩個層面來看就可以知道我們不可能去動開頭字母。
接著我們又可以觀察到將開頭和結尾就定位後，就可以直接忽視這兩個字母（因為如果其他字母要取代它們的話只是浪費步數，還不如不做）。承上例，"mccbbcddddm" 將會變成
"ccbbcdddd"
而 "dmcmcbbcddd" 將變成
"mcmcbbcdd"
結合上述觀察之後我們便可以得到一個貪心演算法（Greedy Algorithm）：
取開頭字母（或結尾字母也可以。甚至交錯地使用開頭、結尾也行。這邊統一是開頭）然後根據第一個觀察找到其對應的字母。如果它是自己一個沒人配對，則代表它是迴文中心，因此將其交換到中心之位置即可；反之，則根據第二個觀察將對應的字母交換到結尾。
然後根據第三個觀察忽視當前地開頭和結尾字母，然後繼續找下一個開頭與其對應的字母去配對。
過程中的交換次數即為所求最小所需次數。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
