Problem Statement
File Compression System
You're developing a lightweight file compression system for a mobile app that needs to save storage space. The system will focus on compressing text files that often contain repeated characters.
Your compression algorithm needs to replace consecutive repeated characters with a single instance of the character followed by the count of repetitions. For example, "aaa" would be compressed to "a3". If a character doesn't have any repetition (i.e., the count is 1), just leave the character as is without adding the count.
Your task is to write a function that takes a string as input and returns the compressed version of the string. If the compressed string would not be smaller than the original string, your function should return the original string.
Examples
Example 1:
Input: "aabcccccaaa"
Output: "a2bc5a3"
Explanation: The string has "aa" followed by "b" followed by "ccccc" followed by "aaa", which compresses to "a2bc5a3".
Example 2:
Input: "abcdef"
Output: "abcdef"
Explanation: No character repeats, so the compressed string would be "a1b1c1d1e1f1", which is longer than the original string. Therefore, return the original string.
Example 3:
Input: "aaaaabbbbaaaabbddc"
Output: "a5b4a4b2d2c"
Explanation: The string compresses to "a5b4a4b2d2c1", but since the count for "c" is 1, we omit it, resulting in "a5b4a4b2d2c".
Constraints
- The string length is between 0 and 10^5 characters.
- The string contains only uppercase and lowercase English letters (a-z, A-Z).
- If the compressed string is not smaller than the original string, return the original string.
- Characters are case-sensitive (e.g., 'a' and 'A' are considered different characters).
Problem Breakdown
To solve this problem, we need to:
- We need to count consecutive occurrences of each character.
- We should only include the count in the compressed string if it's greater than 1.
- We need to compare the length of the compressed string with the original string.
- We can optimize by calculating the compressed length first before actually creating the compressed string.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
File Compression System
You're developing a lightweight file compression system for a mobile app that needs to save storage space. The system will focus on compressing text files that often contain repeated characters.
Your compression algorithm needs to replace consecutive repeated characters with a single instance of the character followed by the count of repetitions. For example, "aaa" would be compressed to "a3". If a character doesn't have any repetition (i.e., the count is 1), just leave the character as is without adding the count.
Your task is to write a function that takes a string as input and returns the compressed version of the string. If the compressed string would not be smaller than the original string, your function should return the original string.
Examples
Example 1:
The string has "aa" followed by "b" followed by "ccccc" followed by "aaa", which compresses to "a2bc5a3".
Example 2:
No character repeats, so the compressed string would be "a1b1c1d1e1f1", which is longer than the original string. Therefore, return the original string.
Example 3:
The string compresses to "a5b4a4b2d2c1", but since the count for "c" is 1, we omit it, resulting in "a5b4a4b2d2c".
Problem Breakdown
Constraints:
- The string length is between 0 and 10^5 characters.
- The string contains only uppercase and lowercase English letters (a-z, A-Z).
- If the compressed string is not smaller than the original string, return the original string.
- Characters are case-sensitive (e.g., 'a' and 'A' are considered different characters).
Key Insights:
We need to count consecutive occurrences of each character.
We should only include the count in the compressed string if it's greater than 1.
We need to compare the length of the compressed string with the original string.
We can optimize by calculating the compressed length first before actually creating the compressed string.
Real-World Application
This problem has several practical applications:
File Compression
Run-length encoding is used in various file formats to compress data with repeated patterns.
Data Storage
Efficient storage of repetitive data in databases and file systems.
Network Transmission
Reducing the size of data transmitted over networks to save bandwidth.