刷題筆記 — String (1)
本系列文章是分享我在 Leetcode 及 Algoexpert 的刷題經驗，這篇文章是 String 篇的第一篇文章。
本系列文章都假定讀者具有基礎的 complexity analysis 概念以及基礎的 Java 能力。為了不讓閱讀時間過長，每篇都只會講解 3 道題目。
每道題目我都會分為 Description(問題描述)、Examples(測資範例)、Solution(解法)、Implementation(實作) 等區塊來進行講解。但如果礙於篇幅問題或是該解法比較不理想（太複雜、效率太差）我可能就只會進行概念上的講解，並不會實際寫出 code implementation。
另外，為了讓讀者能更佳地了解，當我提及程式碼的變數或是相關的數值時，我會將該字反白（如 variable ）。
如欲觀看所有系列文章，可點下面連結前往。
https://medium.com/citychaser/coding-questions/home
好了，廢話不多說，讓我們開始吧！
1. Run-Length Encoding
Description
Run-length encoding 的中文叫做「變動長度編碼法」，是一種「無失真」的資料壓縮方法，所謂無失真就是資料經過壓縮後，能夠再完整地還原成原本的樣子，詳細的介紹可以參考維基百科。
Run-length encoding 將連續的字元用數字來紀錄他的長度並縮減整個字串的長度，例如將 AAAABB 縮減成 4A2B。
今給定一個 non-empty string string，回傳它的 run-length encoding string。
然而如果某個字元連續排列超過了 10 次，直接將這個字串進行 run-length encoding 會出現問題。例如將 AAAAAAAAAAAA 壓縮成 12A，那麼在「解壓縮」的時候，有可能會是 AAAAAAAAAAAA 但也有可能會是 1AA。因此，如果 run-length 超過 9，那麼便從 0 開始重新計算。例如 AAAAAAAAAAAA 就變成 9A3A。
Examples
Input: string = "AAAAABBBBDDDC"
Output: "5A4B3D1C"Solution
這題要注意的地方有兩個，第一點是要紀錄現在 run-length 是否已經到達 9，如果是的話，那就必須存入 9* 並且將 run-length 歸零；第二點是最後一組數字也要記得處理。
有個小細節可以注意，之所以用 ArrayList 來儲存每個 run-length 的字串是因為如果我們一開始宣告一個 String result = ""，然後在每次要加入 run-length 字串時進行字串的 concatenate (result += String.format(“%d%c”, runLength, runChar))，在大部分的程式語言中，字串的 concatenate 其實是 O(N) 的 time complexity (N 為字串長度)，所以隨著字串越來越長，後面的 concatenate 會越來越慢。
但是如果用 ArrayList 的話，每次的 append 都是 O(1)，只有最後一次 join 所有元素成字串時會是 O(N)，當 concatenate 很頻繁且要 concatenate 的字串很長的時候，效率會有顯著的提升。
2. Longest Substring Without Repeating Characters
Description
給定一個 string s，回傳其中不含有重複字元的最長 substring 的長度。
注意，substring 必須是連續的。
e.g. s = pwwkew，wke 為 substring，但 pwke 是 subsequence 而非 substring。
Examples
Input: s = "babad"
Output: "bab" ("aba" 也是正確答案)Input: s = "cbbd"
Output: "bb"Input: s = "a"
Output: "a"
Solution 1 – Brute Force
brute force 的解法自然就是暴力組合出所有的 substring，並一一去檢查每個 substring 裡面有沒有重複的字元。而得到所有 substring 會有 N (原字串長度) 取 2 的組合數，也就是 N(N-1) / 2 組，每一組還需要 n (substring 長度) 個 operation 才能確定是否為 non-repeating。因此，總共的 time complexity 會是 O(N³)。
Solution 2 – Sliding Window
這題要用到的解題技巧是之前講到爛的 two pointer 的一種延伸「sliding window」。
什麼是 sliding window 呢？ 火鍋店裡不是通常都有放冰淇淋的冰櫃嗎？而冰櫃通常都有兩片櫥窗對吧？就是類似這個概念。當你移動左邊跟右邊的櫥窗時，就能夠打開一個區間，拿到各種不同的冰淇淋。
而放到 computer science 裡頭，所謂 sliding window 是指用兩個 pointer 去紀錄櫥窗開啟的範圍。
假設有一個 array arr = [1,2,3,4] ，用兩個 pointer left, right 分別紀錄左右的界限，而在這中間的元素就是我們要的。e.g. 當 left = 0 , right = 2 ，arr 的可見範圍就是 [1,2,3] 。
而 sliding window 跟這題有什麼關係呢？我們可以把 window 內的字元紀錄為「已經出現」的字元，然後每次把 window 擴大一格，看看會不會有重複的字元出現，如果沒有，那我們就繼續把 window 的右邊向右邊滑（擴大）；如果有重複字元，那我們就要把 window 的左邊向右滑（縮小），直到 window 裡沒有重複的字元。
在每次 window 擴大的時候，我們去看看有沒有比當下紀錄到的最大值還要大，如果有的話，就更新最大值。
最後，window 的最大值就是 longest non-repeating substring 的長度，因為 window 代表連續的 substring，而且裡面不會有重複的字元。
接下來，我們用視覺化的方式來示範一次流程。
首先，左右兩個邊界都在最一開頭的位置。
接著，不斷向右擴大 window，到 e 為止，每個字元都沒有重複出現，在每次 window 擴大的同時，我們都要檢查是否大於已經出現的最大值，如果有的話要更新最大值。
到了 e 的下一個 c 的時候，可以看到 window 裡已經有一個 c 了！因此，我們必須要把 left 往右移，直到 window 裡面不存在重複的字元。
於是我們把 left 移到了 index 3 的位置，發現這時 window 裡已經沒有重複的字元。
於是繼續將 right 往右移，擴大整個 window，別忘了要檢查是否大於最大值。
在這時，又發現了重複字元，因此要把 left 往右移，直到 window 裡沒有重複字元。
直到 right 超出字元範圍，代表每個字元都已經檢查過，也就結束。
接著我們來看如何實作，從上面的示範中我們了解到，必須要想辦法記住 window 裡出現過的字元，而最適合這種性質的資料結構便是 Set。
right 跟 left 最多只會移動 N, N-1 次，而伴隨著兩者移動的 operation 也都是 constant time，所以 total time complexity 會是 O(N) 。
另外，我們使用了 HashSet 來紀錄出現過的字元，HashSet 的最大 size 也只會是 string 的長度，因此 space complexity 也為 O(N)。
3. Group Anagrams
Description
給定一個 array of string strs，將其中的 anagrams 進行分群並回傳。
所謂的 anagram 是指用同樣的字元組成另一個單字，如：tea 可以重組成 eat，他們兩個就是一組 anagram；listen & silent 也是一組 anagram。
strs 中只會包含小寫的英文字母。
Examples
Input: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["bat"], ["tan", "nat"], ["eat", "tea", "ate"]] // can be in any orderSolution 1 – Group By Sorted String
所謂的 anagram 就是要用同一組字元來進行重組，所以如果將 anagram 進行 sorting (in alphabetical order) 的話，結果應該會是同一組字串才對。e.g. tea 跟 eat 進行 sorting 後應該都是 aet；listen 跟 silent 進行 sorting 後應該都是 eilnst。
所以我們迭代 strs 的每個 string，如果他們 sorted 後的 string 是同一個，那麼就是同一組 anagram。
我們可以利用 hash table 來完成這件事，key 就是 sorted 後的 string、value 則是儲存該組 anagram 的 list / array of original strings。
這個解法的 time complexity 會是 O(NKlogk)，其中 N 代表 strs 的長度，而 K 是 strs 中最長的 string 的長度（因為 big O 是代表運算時間上限，所以是用最長的去算）。
迭代 strs 中的每個 string 需要 N 次，而每一次我們都要將這個 string 進行 sorting，這個動作通常需要 O(KlogK)，相乘後會是 O(NKlogK)。
至於 space complexity，因為要存下共 N 個 string，每個 string 長度最大為 K ，因此 space complexity 為 O(NK)。
Solution 2 – Group By Character Counts
同樣利用 anagram 的特性，如果兩個 string 為同一組 anagram，那麼他們所出現的字元及對應的出現字數要是一樣的。
我們將「出現字數」化為一個 string，用 #{a}#{b}…#{z} 來代表，其中 {} 代表該字元出現的次數。e.g. aab -> #2#1#0#0…#0, abc -> #1#1#1#0…#0。
和上面的解法其實概念是一樣的，只是這次我們把 hash table 的 key 從 sorted string 替換成這個 26 個字元出現的 occurrence string。
這個解法的 time complexity 會比上面略好，因為我們在每一個 string 不需要再去進行 sorting，而只需要紀錄每個字元的 occurrence，而紀錄每個字元的 occurrence 只需要 loop through string once，所以 time complexity 為 O(K)，相乘後總 time complexity 為 O(NK)。
至於 space complexity 則與上面的解法相同，都是 O(NK)。
今天的刷題分享就到這邊了，如果有什麼指教或是建議，歡迎在這篇文章底下留言；如果覺得這篇文章不錯，也歡迎給我點掌聲！
