# #3 Run-Length Encoding

###### tags: `String` `Easy`

## Problem
Write a function that takes in a non-empty string and returns its run-length encoding.

From Wikipedia, "run-length encoding is a form of lossless data compression in which runs of data are stored as a single data value and count, rather than as the original run." For this problem, a run of data is any sequence of consecutive, identical characters. So the run ``"AAA"`` would be run-length-encoded as ``"3A"``.

To make things more complicated, however, the input string can contain all sorts of special characters, including numbers. And since encoded data must be decodable, this means that we can't naively run-length-encode long runs. For example, the run ``"AAAAAAAAAAAA"`` (12 `A`s), can't naively be encoded as ``"12A"``, since this string can be decoded as either ``"AAAAAAAAAAAA"`` or ``"1AA"``. Thus, long runs (runs of 10 or more characters) should be encoded in a split fashion; the aforementioned run should be encoded as `"9A3A"`.

### Sample Input

string = "AAAAAAAAAAAAABBCCCCDD"

### Sample Output

"9A4A2B4C2D"

<br>

:::spoiler **Optimal Space & Time Complexity**

O(n) time | O(n) space - where n is the length of the input string

:::

<br>

:::spoiler Hint 1
Traverse the input string and count the length of each run. As you traverse the string, what should you do when you reach a run of length 9 or the end of a run?

:::

<br>

:::spoiler Hint 2
When you reach a run of length 9 or the end of a run, store the computed count for the run as well as its character (you'll likely need a list for these computed counts and characters), and reset the count to 1 before continuing to traverse the string.
:::

<br>

:::spoiler Hint 3
Make sure that your solution correctly handles the last run in the string.
:::

<br>

<hr/>

## Solutions

### Official

// O(n) time | O(n) space - where n is the length of the input string
function runLengthEncoding(string) {
  // The input string is guaranteed to be non-empty,
  // so our first run will be of at least length 1.
  const encodedStringCharacters = [];
  let currentRunLength = 1;
  
  for (let i = 1; i < string.length; i++) {
    const currentCharacter = string[i];
    const previousCharacter = string[i - 1];
    
    if (currentCharacter !== previousCharacter || currentRunLength === 9) {
      encodedStringCharacters.push(currentRunLength.toString());
      encodedStringCharacters.push(previousCharacter);
      currentRunLength = 0;
    }
      
    currentRunLength++;
  }

  // Handle the last run.
  encodedStringCharacters.push(currentRunLength.toString());
  encodedStringCharacters.push(string[string.length - 1]);
  
  return encodedStringCharacters.join('');
}

<br>

---

### Everyone's

#### Solution type 1

- ~~Sorry I don't understand. Explain yourself~~

:::spoiler Hao

function runLengthEncoding(string) {
  /**
   * O(n) time, O(n) space
   */
  const charArr = string.split('');
  let res = '';
  const record = {
    charCode: null,
    count: 0,
  };
  const resetRecord = (newCharCode) => {
    if (record.charCode !== null && record.count) res += `${record.count}${String.fromCharCode(record.charCode)}`;
    if (newCharCode) {
      record.charCode = newCharCode;
      record.count = 1;
    }
  };
  charArr.forEach((char) => {
    const charCode = char.charCodeAt(0);
    if (record.charCode !== charCode || record.count === 9) resetRecord(charCode);
    else record.count += 1;
  });
  resetRecord();

  return res;
}

- I think because `res` consists of mutating string inside for-loop, the time complexity should be O(n^2)
- Question: why using `charCodeAt`
:::

<br>

---
#### Solution type 2

(Not a good appoach)
- use sort of pointer-like concept to get the first and last index of consecutive char, than calculate the length
- compare first new character with current character
- Push result into array and use `array.join("")` for final result

:::spoiler 東

const MAX_NUM = 9;
function runLengthEncoding(string) {
  const charCntRes = [];
  let firstCharIdx = 0;
  for (let i = 0; i < string.length; i++) {
    if (string[firstCharIdx] !== string[i]) {
      charCntRes.push(`${i - firstCharIdx}${string[firstCharIdx]}`);
      firstCharIdx = i;
    }
    else if (string[firstCharIdx] === string[i] 
              && (i - firstCharIdx + 1) === MAX_NUM 
              && i !== string.length) {
      charCntRes.push(`${MAX_NUM}${string[firstCharIdx]}`);
      firstCharIdx = i + 1;
    } 
    
    if (i === string.length - 1 ) {
      charCntRes.push(`${i - firstCharIdx + 1}${string[firstCharIdx]}`);
    }
  }
  return charCntRes.join("");
}

:::

---

#### Solution type 3

- use count to calculate
- compare first new character with current character
- continue concat the result string

:::spoiler Becky

function runLengthEncoding(string) {
  let result = '';
    let len = string.length;
    if (len > 0) {
      let value = string[0];
      let count = 1;
      for (let i = 1; i< len; i++){
        var letter = string[i];
        if(letter == value){
          count ++;
          if(count > 9){
            result += (count-1) + letter;
            count = 1;
          }
        }else{
          result += count + value;
          count = 1;
          value = letter;
        }
      }
      result += count + value;
    }
  return result;
}

- According to the description of question, `if(len > 0)` is not needed since the input will always be a non-empty string
- use `===`
:::

<br>

---

#### Solution type 4

- use count to calculate
- compare first new character with current character
- Push result into array and use `array.join("")` for final result

:::spoiler SOL

function runLengthEncoding(string) {
  let curLength = 0;
  let preCharacter = string[0];
  let result = [];
  for (let index = 0; index < string.length; index++) {
    const character = string[index];
    if (preCharacter === character) {
      if (curLength === 9) {
        result.push(`${curLength}${preCharacter}`);
        curLength = 1;
      } else {
        curLength++;
      }
    } else {
      result.push(`${curLength}${preCharacter}`);
      preCharacter = character;
      curLength = 1;
    }
    if (index + 1 === string.length) {
      result.push(`${curLength}${preCharacter}`);
    }
  }
  return result.join("");
}

:::

---

#### Solution type 5

- Declare count to calculate
- compare current and next character
- Push result into array and use `array.join("")` for final result

:::spoiler Raiy

function runLengthEncoding(string) {
  // Time O(n) | Space O(n)

  let count = 1;
  let currentLetter = "";
  let result = [];

  for (let i = 0; i < string.length; i++) {
    currentLetter = string[i];
    if (currentLetter === string[i + 1]) {
      count++;
      if (count === 9) {
        result.push(`9${currentLetter}`);
        count = 1;
        i++;
      }
    } else {
      result.push(`${count}${currentLetter}`);
      count = 1;
    }
  }
  return result.join("");
}

- Question: why need `i++` on line 15?

:::

<br>

:::spoiler YC
Indentical to offcial solution

/*
    time: O(n) - where n is the length of the input string 
    space: O(n) - where n is the length of the input string
*/

function runLengthEncoding(string) {
  const MAX_LENGTH = 9;
  const encoded = [];
  
  let count = 1;
  for (let i = 1; i < string.length; i++) {
    const currChar = string[i];
    const prevChar = string[i-1];
    if (currChar !== prevChar || count === MAX_LENGTH) {
      encoded.push(count);
      encoded.push(prevChar);
      count = 0;
    };
    count++;
  }
  const lastChar = string[string.length - 1];
  encoded.push(count);
  encoded.push(lastChar);
  return encoded.join("");
}

:::

<br>

:::spoiler 月
In my perspective, this is a even-better solution comparing to offcial solution

function runLengthEncoding(string) {
  // Time O(n) Space O(n) n is the length of the string
  let i = 0;
  let count = 1;
  const answer = [];
  while(i < string.length){
    if(string.charAt(i) !== string.charAt(i + 1) || count === 9){
      answer.push(count + string.charAt(i));
      count = 1;
    }else{
      count++;
    }
    i++;
  }
  return answer.join("")
}

:::

<br>

---

## Supplement / Discussion

### Mutate string is O(n) Time operation
> String in JavaScript is **immutable**

> ***In JavaScript, strings are immutable objects, which means that the characters within them may not be changed and that any operations on strings actually create new strings**. Strings are assigned by reference, not by value. In general, when an object is assigned by reference, a change made to the object through one reference will be visible through all other references to the object. Because strings cannot be changed, however, you can have multiple references to a string object and not worry that the string value will change without your knowing it* -- Rhino book

#### Immutable
- Immutables are the objects whose state cannot be changed once the object is created.
- String and Numbers are Immutable.
- You can make a variable name point to a new value, but the previous value is still held in memory. Hence the need for garbage collection.

#### Example

let immutableString = "Hello";
// In the above code, a new string is created.

immutableString += "World";
// We are now appending "World" to the existing value.

This looks like we're mutating the string 'immutableString', but we're not. Instead, the following events occurs:

1. Existing value of `immutableString` is retrieved
2. "World" is appended to the existing value of `immutableString`
3. The resultant value is then allocated to a new block of memory
4. `immutableString` object now points to the newly created memory space
5. Previously created memory space is now available for garbage collection.

#### Actual speed test

Referencing [Stack overFlow](https://stackoverflow.com/questions/51185/are-javascript-strings-immutable-do-i-need-a-string-builder-in-javascript)

---

**Conclusion**

Although JS engine in nowadays browsers is processing appending string really fast, and might be faster than using `array.push` + `array.join`. Yet consider the concept of Big O. Mutating string in any term should still be considered as a O(n) time operation.