You are given a string word. Build a new string comp by repeatedly taking a non empty prefix of the remaining word, removing that prefix from word, and appending an encoded form of the prefix to comp.

A prefix can be encoded only if it consists of a single repeated character, and its length is at most $9$. If the chosen prefix has length k and character c, append the string representation of k followed by c to comp.

Return the final value of comp after the entire word has been processed.

Note: Each encoded group must have length at most $9$, so runs longer than $9$ must be split into multiple groups.

Constraints:

• $1 \leq$ word.length $\leq 2 \cdot 10^5$

• word consists only of lowercase English letters.

Input: word = "z"-str
Output: "1z"-str
Explanation: The entire string is one run of length 1 ("z"), so it encodes as 1z.

Input: word = "ppppppppp"-str
Output: "9p"-str
Explanation: There are 9 consecutive 'p' characters, and since the maximum group size is 9, it encodes as 9p.

Input: word = "mmmmmmmmmmmm"-str
Output: "9m3m"-str
Explanation: There are 12 consecutive 'm' characters. Runs longer than 9 must be split, so the first 9 encode as 9m and the remaining 3 as 3m.

Input: word = "aaabccccccccccddeeeeeeeeeffg"-str
Output: "3a1b9c1c2d9e2f1g"-str
Explanation: Encoding each consecutive run and splitting any run longer than 9 gives "aaa" → 3a, "b" → 1b, "cccccccccc" (10 c’s) → 9c1c, "dd" → 2d, "eeeeeeeee" (9 e’s) → 9e, "ff" → 2f, and "g" → 1g. Concatenating gives "3a1b9c1c2d9e2f1g".

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.