#3163

Medium

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

String Compression III

Compress a string by repeatedly taking maximal same-character prefixes, following a string-driven solution strategy efficiently.

string

Problem Statement

Given a string word consisting of lowercase English letters, repeatedly compress it using the following rule: choose a prefix of identical characters, at most length 9, remove it, and append its length followed by the character to a new string comp. Continue until the original string is empty.

Return the final compressed string comp. For example, given word = "abcde", output should be "1a1b1c1d1e". For word = "aaaaaaaaaaaaaabb", output should be "9a5a2b". The goal is to apply a string-driven solution strategy to always select the largest available prefix of identical characters.

Examples

Example 1

Input: word = "abcde"

Output: "1a1b1c1d1e"

Initially, comp = "" . Apply the operation 5 times, choosing "a" , "b" , "c" , "d" , and "e" as the prefix in each operation. For each prefix, append "1" followed by the character to comp .

Example 2

Input: word = "aaaaaaaaaaaaaabb"

Output: "9a5a2b"

Initially, comp = "" . Apply the operation 3 times, choosing "aaaaaaaaa" , "aaaaa" , and "bb" as the prefix in each operation.

Constraints

1 <= word.length <= 2 * 105
word consists only of lowercase English letters.

Solution Approach

Greedy prefix selection

Iterate through the string and always pick the maximal same-character prefix up to 9 characters. Append its length and character to the compressed string. This prevents suboptimal smaller cuts that increase the compressed size.

Iterative string reconstruction

After selecting each prefix, remove it from the remaining string and continue compressing. Building comp incrementally ensures correctness and follows the string-driven solution strategy explicitly.

Optimize for long runs

For runs longer than 9 characters, split into multiple operations of up to 9 characters each. This strategy maintains correct compression counts and handles large consecutive character sequences efficiently.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each character is processed once. Space complexity is O(n) since the compressed string comp may store all characters in the worst case.

What Interviewers Usually Probe

Ask candidate to explain why cutting smaller prefixes first can lead to longer output.
Check if candidate recognizes maximal same-character prefix strategy.
Probe understanding of handling runs longer than 9 characters efficiently.

Common Pitfalls or Variants

Common pitfalls

Cutting prefixes smaller than 9 when a longer run exists, producing non-optimal compression.
Failing to handle consecutive runs longer than 9, causing incorrect counts in comp.
Appending characters without counts when a run length is one, breaking the compression format.

Follow-up variants

Allow compression for mixed-case letters and include case-sensitive counts.
Limit maximum prefix length to a value other than 9, adjusting the strategy accordingly.
Compress strings with numbers and letters, extending the character handling logic.

FAQ

What is the main strategy behind String Compression III?

Use a string-driven approach by always selecting the longest same-character prefix up to 9 characters for compression.

How do I handle runs longer than 9 characters?

Split the run into multiple prefixes of length 9 or less, appending each count and character to the compressed string.

Can the input contain uppercase letters?

No, the problem constraints specify only lowercase English letters.

Why is greedy prefix selection important?

Choosing smaller prefixes first can produce longer output; greedy maximal selection ensures minimal compressed length.

What pattern does GhostInterview recognize in this problem?

It recognizes the string-driven solution strategy, focusing on maximal same-character prefix selection and efficient iteration.

terminal

Solution

Solution 1: Two Pointers

We can use two pointers to count the consecutive occurrences of each character. Suppose the current character $c$ appears consecutively $k$ times, then we divide $k$ into several $x$, each $x$ is at most $9$, then we concatenate $x$ and $c$, and append each $x$ and $c$ to the result.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def compressedString(self, word: str) -> str:
        g = groupby(word)
        ans = []
        for c, v in g:
            k = len(list(v))
            while k:
                x = min(9, k)
                ans.append(str(x) + c)
                k -= x
        return "".join(ans)

Solution 2: Two Pointers

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def compressedString(self, word: str) -> str:
        g = groupby(word)
        ans = []
        for c, v in g:
            k = len(list(v))
            while k:
                x = min(9, k)
                ans.append(str(x) + c)
                k -= x
        return "".join(ans)

Solution 3: RegExp

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def compressedString(self, word: str) -> str:
        g = groupby(word)
        ans = []
        for c, v in g:
            k = len(list(v))
            while k:
                x = min(9, k)
                ans.append(str(x) + c)
                k -= x
        return "".join(ans)

Continue Practicing

#3168 minimum number of chairs in a waiting room #3170 lexicographically minimum string after removing stars #3174 clear digits