162. Run Length Encoding for List of Characters

Run Length Encoding for List of Characters

Design a RunLengthEncoding class that implements run-length encoding for a list of characters.

Run-length encoding compresses consecutively repeated characters by storing each character with its consecutive count.

For example, the list ["A", "B", "B", "C", "A"] can be compressed as:
["A,1", "B,2", "C,1", "A,1"]

You also need to implement a get method that takes a compressed string and an index i, and returns the character stored at index i in the original uncompressed list.

The compressed string used by get is different from the encoded list returned by getEncodedList.

RunLengthEncoding()

Methods

List<String> getEncodedList(List<String> characters)

Returns the compressed run-length encoding of the given list of characters.
each character will be from [a-z, A-Z]
Each string in characters represents exactly one character.
Each encoded group should be returned as a string in the format "character,count".
The order of encoded groups must be the same as their order in the original list.
Sample Output: ["A,1", "B,2", "C,1", "A,1"]

String get(String compressedString, int i)

Returns the character at index i in the original uncompressed list represented by compressedString.
The index i is zero-based.
If index i is invalid, return an empty string "".
The compressedString uses the format "character:count|character:count|...".
each character will be from [a-z, A-Z]
For example, "A:1|B:2|C:1|A:1" represents the original list ["A", "B", "B", "C", "A"].
The compressed string passed to get is independent from the list passed to getEncodedList.

Constraints

0 ≤ characters.size() ≤ 100,000
characters.get(j).length() = 1 for every valid index j
0 ≤ compressedString.length() ≤ 1,000,000
Each group inside compressedString is valid and follows the format "character:count".
Each character inside compressedString has length 1.
Each count inside compressedString is a positive integer.
If compressedString is empty, it represents an empty original list.
Parameter values will never be null.
The number of encoded groups is at most the size of the original uncompressed list.

Examples

Example 1

RunLengthEncoding()
getEncodedList(characters = ["A", "B", "B", "C", "A"]) returns ["A,1", "B,2", "C,1", "A,1"]
get(compressedString = "A:1|B:2|C:1|A:1", i = 2) returns "B"

Explanation:
The compressed string represents ["A", "B", "B", "C", "A"]. Index 2 contains "B".

Example 2

RunLengthEncoding()
getEncodedList(characters = ["A", "A", "A", "A"]) returns ["A,4"]
get(compressedString = "A:4", i = 0) returns "A"
get(compressedString = "A:4", i = 3) returns "A"
get(compressedString = "A:4", i = 4) returns ""

Explanation:
The compressed string represents four characters. Indices 0 through 3 are valid, and index 4 is invalid.

Example 3

RunLengthEncoding()
getEncodedList(characters = ["A", "A", "B", "B", "B", "C", "C", "A"]) returns ["A,2", "B,3", "C,2", "A,1"]
get(compressedString = "A:2|B:3|C:2|A:1", i = 4) returns "B"
get(compressedString = "A:2|B:3|C:2|A:1", i = 6) returns "C"
get(compressedString = "A:2|B:3|C:2|A:1", i = 7) returns "A"

Explanation:
The first two "A" values form one group. The last "A" appears after "C", so it forms a separate group.

Example 4

RunLengthEncoding()
getEncodedList(characters = []) returns []
get(compressedString = "", i = 0) returns ""
get(compressedString = "", i = -1) returns ""

Explanation:
An empty compressed string represents an empty original list, so every index is invalid.

Example 5

RunLengthEncoding()
getEncodedList(characters = ["X", "Y", "Y", "Y", "Z"]) returns ["X,1", "Y,3", "Z,1"]
get(compressedString = "M:2|N:5|P:1", i = 6) returns "N"

Explanation:
The compressed string passed to get is independent from the characters passed to getEncodedList. In "M:2|N:5|P:1", index 6 contains "N".