# String Compression 字串壓縮
#### 題目説明
- aabcccccaaa -> a2b1c5a3
- 若壓縮後的字串沒有變短則返回原字串
- 可以假設字串中只包含大小寫英文字母(a 至 z)

#### 解題説明
- 迭代字串，複製到新字串。
- 迭代過程中檢查當前字符與下一個字符是否一致。

##### Solution

function compressBad(str){
    let compressedString = ""
    let countConsecutive = 0
    for(let i=0 ; i<str.length ; i++){
        countConsecutive += 1
        if( i+1 >= str.length || str.charAt(i) != str.charAt(i+1)){
            compressedString += str.charAt(i) + countConsecutive
            countConsecutive = 0
        }
    }
    return compressedString.length < str.length ? compressedString :  str
}

console.log(compressBad("gooooood")) //g1o6d1
console.log(compressBad("QOO"))  //QOO

:::warning
**運算符+連接字串** 的時間複雜度

由於字串是**不可變量**，在串接字串（S1+S2+S3+…+SN）的時候實際上是經歷：
1. 申請新的一塊内存（RAM）
2. 將上一次操作的結果與本次操作的結果複製到新的内存空間

因此當 N 個字串串接的過程中，會產生：
- N-1 個中間結果
- 申请(複製) N-1 次内存

相當於：
- S1 被複製 N-1 次，S2 被複製 N-1 次...
- **時間複雜度接近 O(n^2)**

:::
##### Solution +

:::success
**使用 join() 方法**
- 會先計算需要申請的總的內存空間
- 一次性申請所需內存並將字符序列，並將字符序列
- 時間複雜度為O(n)
:::

function compressBad(str){
    let compressedArray = []
    let countConsecutive = 0
    for(let i=0 ; i<str.length ; i++){
        countConsecutive += 1
        if( i+1 >= str.length || str.charAt(i) != str.charAt(i+1)){
            compressedArray.push(str.charAt(i),countConsecutive)
            countConsecutive = 0
        }
    }
    return compressedArray.length < str.length ? compressedArray.join('') :  str
}

console.log(compressBad("gooooood"))
console.log(compressBad("QOO"))

[Javascript Does Not Need a StringBuilder](https://josephmate.github.io/java/javascript/stringbuilder/2020/07/27/javascript-does-not-need-stringbuilder.html)