Compress a String by Run-Length Counts, Keeping the Original When Not Shorter

Implement basic string compression based on runs of repeated characters. Replace every maximal run of consecutive identical characters with that character followed by the length of the run, written in decimal. For example, aabcccccaaa becomes a2b1c5a3.

If the compressed string is not strictly shorter than the original string, return the original string unchanged.

In the interview you are also expected to state the time and space complexity of your implementation, walk through the edge cases it handles, and discuss how the code could be optimized.

Function Signature

def compress(s: str) -> str:

Rules

• A run is a maximal block of consecutive equal characters. Every run is encoded, including runs of length 1 (a single b becomes b1).
• Matching is case-sensitive: a and A are different characters, so aA consists of two runs.
• A run longer than 9 is written with all of its digits: a run of twelve a characters becomes a12.
• Compare lengths only after compressing the whole string. Return the compressed string if its length is strictly less than len(s); if it is equal or longer, return s.
• The empty string is returned as the empty string.

Constraints

• 0 <= len(s) <= 10^5
• s contains only English letters, a to z and A to Z.

Examples

Example 1

Input:  s = "aabcccccaaa"
Output: "a2b1c5a3"

The runs are aa, b, ccccc and aaa. The compressed form has 8 characters, fewer than the original 11.

Example 2

Input:  s = "aabb"
Output: "aabb"

The compressed form a2b2 has 4 characters, the same as the original, so the original is returned.

Example 3

Input:  s = "aaaaaaaaaaB"
Output: "a10B1"

The input is ten a characters followed by one B. The run of ten is written as a10, and the compressed form has 5 characters, fewer than the original 11.

Run-Length Compression Kept Only When Strictly Shorter

Given a string s, compress it using runs of repeated characters: replace every maximal run of consecutive identical characters with that character followed by the length of the run, written in decimal. For example, aabcccccaaa becomes a2b1c5a3.

If the compressed string is not strictly shorter than s, return s unchanged; otherwise return the compressed string.

Rules

• A run is a maximal block of consecutive equal characters. Every run is encoded, including runs of length 1 (a single b becomes b1).
• Matching is case-sensitive: a and A are different characters, so aA consists of two runs.
• A run longer than 9 is written with all of its digits: a run of twelve a characters becomes a12.
• Compare lengths only after compressing the whole string. Return the compressed string if its length is strictly less than len(s); if it is equal or longer, return s.
• The empty string is returned as the empty string.

Example 1

Input:  s = "aabcccccaaa"
Output: "a2b1c5a3"

The runs are aa, b, ccccc and aaa. The compressed form has 8 characters, fewer than the original 11.

Example 2

Input:  s = "aabb"
Output: "aabb"

The compressed form a2b2 has 4 characters, the same as the original, so the original is returned.

Constraints

• 0 <= len(s) <= 10^5
• s contains only English letters, a to z and A to Z.

Every run length and string length is at most 10^5, so no value exceeds 2^31 - 1 and a 32-bit int is enough in every language.

Hints

1. A run ends where the next character differs from the current one or where the string ends; make sure the last run is written out too.
2. Run lengths of 10 or more need every decimal digit, and 'a' and 'A' never belong to the same run.
3. Build the whole compressed string before comparing lengths, and remember that an equal length keeps the original.

Approach

Scan s from left to right with an index i. From i, advance a second index j while s[j] equals s[i]; the block s[i:j] is then a maximal run, so append s[i] followed by the decimal string of j - i, and continue from j. Invariant: whenever the outer loop is at i, the buffer holds exactly the encoding of the maximal runs of s[0:i], and s[i] starts a new run (either i is 0 or s[i] differs from s[i-1]). Every character belongs to exactly one maximal run and runs are emitted in order, so when i reaches len(s) the buffer is the full compression, including the final run, which is flushed by the same loop rather than by a special case. Only then compare lengths: return the buffer if it is strictly shorter than s, otherwise return s. Edge cases: the empty string gives an empty buffer that is not shorter than itself, so the empty string is returned; a single character gives x1, which is longer, so the original is returned; ties such as aabb -> a2b2 keep the original; runs of 10 or more emit every digit of their length; comparison is case-sensitive, so a and A always start separate runs. Collecting pieces in a list, StringBuilder or std::string avoids quadratic repeated concatenation. A possible optimization is to stop building once the buffer reaches len(s) characters, since the original would be returned anyway.

• Time complexity: O(n)
• Space complexity: O(n)