Run-length encoding (35 points). Data compression is used behind the scenes in computer systems quite often, computer files and other kinds of data can be compressed to a smaller size for easy storage or transportation. Later, they are decompressed and used in their original form. One basic idea is to find parts of the data that are identical to each other and use some kind of trick to describe that more efficiently.

Run-length encoding (RLE) encodes a run of repetitions with the length of that run. RLE is a simple compression algorithm (an algorithm which takes a block of data and reduces its size, producing a block that contains the same information in less space). It works by replacing repetitive sequences of identical data items with short tokens that represent entire sequences. Applying RLE to a string involves finding sequences in the string where the same character repeats. Replace each such sequence by a token consisting of:

the number of characters in the sequence
the repeating character
If a character does not repeat, it appears as a single character in the compressed string with no number preceding it.

For example, consider the following string:


After applying the RLE algorithm, this string is converted into:

q9w5e2rt5y4qw2Er3T
In the compressed string, "9w" represents a sequence of 9 consecutive lowercase "w" characters. "5e" represents 5 consecutive lowercase "e" characters, etc.

Write a RLE library by implementing the following API:

public class RunLengthEncoding {

// Encodes the original string by finding sequences in the string
// where the same character repeats.
// Replace each such sequence by a token consisting of: the number
// of characters in the sequence followed by the repeating character.
// Write an iterative encode method.
// Returns the encoded string.
public static String encode (String original)

// Decodes the original string encoded with the encode method.
// Returns the decoded string.
// YOUR decode METHOD MUST BE RECURSIVE.
// Do not use while, do/while, or for loops.
public static String decode (String original)

// Tests each of the API methods by directly calling them.
public static void main (String[] args)
}
For decode, you may assume that the character counts will be single-digit numbers (a character will not repeat more than 9 times consecutively). Hint #1: remember that characters are represented by numeric codes. You can decrement a character variable as follows:

char c = '7';
c--; // c will now hold the character '6'
Hint #2: You can check if a character is a digit by using the isDigit() method from the Character class as follows:

char c = '7';
Character. isDigit(c); // returns true
Hint #3: You probably will not need to use this hint for this problem. However, a fast way to convert a digit character into the numeric value of the digit is to subtract the character code for the digit zero:

char c = '7'; // this has the character code 55, not 7
int x = c - '0'; // this produces the number 7