problem

輸入為一個不為空的字串，回傳該字串經過變動長度編碼 (run-length encoding) 的結果。

sample input:
string = 'AAAAAAAAAAAAABBCCCCDD'

sample output:
'9A4A2B4C2D'

變動長度編碼是一種無失真資料壓縮的方式，將資料串 (runs of data)，也就是一連串連續、相同的資料，儲存為數量 + 單一資料，來實現壓縮。舉例來說，'AAA' 會被編碼為 '3A'。而所謂無失真指的是輸出可以恢復成輸入，輸入也可以變為輸出。

如果觀察上方範例，13 個 A 被編碼為 '9A4A' 而非 '13A'，是因為輸入字串可以包含任何字元 (當然也就包含數字)，所以如果要將 '13A' 解碼，就會無法確定是 'AAAAAAAAAAAAA' 還是 '1AAA'。因此編碼時長度超過九的資料串需將它拆開表達。

solution

解法為遍歷字串，在陣列中記錄每個資料串的長度和字元，最後再將陣列合併為新字串回傳。之所以使用陣列而非字元串接，原因為這一題解一中提到的差異。
而因為已知輸入字串不為空字串，所以資料串長度 length 可以從 1 開始。接下來步驟為：

1. 從第二個字元開始遍歷字串，每個字元 i 跟前一個字元 i - 1 比較，如果相同，則 length++。如果 length 為 9，則將 length 和 i - 1 存進陣列中。
2. 承上步驟，如果 i 和 i - 1 不同，代表資料串結束，則將 length 和 i - 1 存進陣列中。
3. 前兩個步驟中，如果有儲存進陣列，都將 length 重新設為 1，且 i 移往下一個字元，開始計算下一個組資料串。
4. 最後一組資料串並不會觸發步驟 1, 2 中的條件記錄進陣列中，所以遍歷結束後，還要再將 length 和最後一個字元存進陣列中。另外，這個步驟也可以處理只有一個字元的輸入字串。

n 為輸入字串長度
time: O(n) 遍歷需要 n 時間，最後合併長度 n 的陣列也需要 n 時間，2n 省略為 n。
space: O(n) 假設最差情況輸入字串每個字元都不同，即每個資料串長度都為一，則會需要 2n 空間，省略為 n。

function runLengthEncoding(string) {
  const chars = [];
  let length = 1;
  for (let i = 1; i < string.length; i++) {
    const currentChar = string[i];
    const previousChar = string[i - 1];
    if (currentChar !== previousChar || length === 9) {
      chars.push(length.toString());
      chars.push(previousChar);
      length = 0;
    }
    length++;
  }
  // 處理最後一組資料串
  chars.push(length.toString());
  chars.push(string[string.length - 1]);
  return chars.join('');
}