Salesforce OA 面试真题解析：String Compression 字符串压缩

Compression

To reduce the size of messages transmitted over the internet, a compression algorithm encodes consecutive repeating characters in a string.

Your task is to compress the given string using this rule:

• Scan the string from left to right and group consecutive identical characters.
• If a character appears once, add just the character to the output.
• If a character appears more than once in a row, add the character followed by the number of consecutive occurrences.

Example

Suppose message = "aabbccca".

Output: a2b2c3a

Complete the compressedString function below.

The function is expected to return a STRING.

The function accepts STRING message as parameter.

Constraints

• All characters in message are in the range ascii[a-z].
• length of message <= 10^5

这道题要求对字符串做简单的游程压缩：从左到右扫描，把连续相同的字符合并成一段；如果某段长度为 1，就直接输出该字符，如果长度大于 1，就输出字符加上次数。实现上只需要一次线性遍历，用两个指针统计每一段连续字符的长度，再用 StringBuilder 拼接结果即可，时间复杂度为 O(n)，适合处理长度最高达到 10^5 的字符串。