Mid/SeniorString
String Compression III
Given a string word, compress it using the following algorithm:
- Begin with an empty string
comp. - While
wordis not empty, use the following operation: - Remove a maximum length prefix of
wordmade of a single charactercrepeating at most 9 times. - Append the length of the prefix followed by
ctocomp.
Return the string comp.
Example 1
Input
word = "abcde"Output
"1a1b1c1d1e"Initially,
comp = ""; applying the operation to prefixes "a", "b", "c", "d", and "e" appends "1" followed by each character.Example 2
Input
word = "aaaaaaaaaaaaaabb"Output
"9a5a2b"The maximum valid prefixes are
"aaaaaaaaa", "aaaaa", and "bb", which append "9a", "5a", and "2b" to comp.Constraints
- 1 <= word.length <= 2 * 10^5
- word consists only of lowercase English letters.