# Run Length Encoding

Understand how Run Length Encoding works and how it can efficiently compress repetitive data.

Strings
easy

Published At

6/4/2021

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Â As), 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

js
``string = "AAAAAAAAAAAAABBCCCCDD"``
js
``string = "AAAAAAAAAAAAABBCCCCDD"``

### Sample Output

js
``"9A4A2B4C2D"``
js
``"9A4A2B4C2D"``

### Hints

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?

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.

Hint 3

Make sure that your solution correctly handles the last run in the string.

Optimal Space & Time Complexity

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

Solution-1
js
``````function runLengthEncoding(string) {
let newString = ''
let currentLetter = string[0]
let currentCount = 0
for (let i = 0; i < string.length; i++) {
if (currentLetter === string[i]) {
if (currentCount >= 9) {
newString += 9 + currentLetter;
currentCount = 0
}
currentCount += 1
} else {
newString += currentCount + currentLetter;
currentLetter = string[i]
currentCount = 1
}
}
newString += currentCount + currentLetter
return newString
}``````
Solution-1
js
``````function runLengthEncoding(string) {
let newString = ''
let currentLetter = string[0]
let currentCount = 0
for (let i = 0; i < string.length; i++) {
if (currentLetter === string[i]) {
if (currentCount >= 9) {
newString += 9 + currentLetter;
currentCount = 0
}
currentCount += 1
} else {
newString += currentCount + currentLetter;
currentLetter = string[i]
currentCount = 1
}
}
newString += currentCount + currentLetter
return newString
}``````

âď¸

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek đ

## Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

• In-depth looks at my covert projects and musings to ignite your imagination.
• Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
• A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.