Solution Approach
Solution Overview
There are 2 main approaches to solve this problem:
- Two-Pointer Approach - Complex approach
- Two-Pass Approach - Complex approach
Approach 1: Two-Pointer Approach
We can use a two-pointer approach to iterate through the string and count consecutive characters. We'll maintain a pointer to the current character and another to track the count of consecutive occurrences.
Input: "aabcccccaaa"
Count 'a': 2, Add "a2" to result
Count 'b': 1, Add "b" to result
Count 'c': 5, Add "c5" to result
Count 'a': 3, Add "a3" to result
Final result: "a2bc5a3"
Algorithm:
- Initialize an empty result string.
- Initialize a counter to 1 (to count consecutive characters).
- Iterate through the string from the second character to the end.
- If the current character is the same as the previous one, increment the counter.
- If the current character is different from the previous one, append the previous character to the result.
- If the counter is greater than 1, also append the counter to the result.
- Reset the counter to 1 and continue.
- After the loop, handle the last character and its count.
- Compare the length of the compressed string with the original string and return the shorter one.
Time Complexity:
where n is the length of the input string. We need to iterate through each character once.
Space Complexity:
In the worst case, the compressed string could be as long as the original string (if there are no repeated characters).
Approach 2: Two-Pass Approach
To optimize the solution, we can first calculate the length of the compressed string without actually creating it. If the compressed length is not smaller than the original length, we can return the original string immediately. Otherwise, we perform the compression in a second pass.
Algorithm:
- First pass: Calculate the length of the compressed string.
- Initialize a counter to 1 and a compressed length to 0.
- Iterate through the string and count consecutive characters.
- For each group of consecutive characters, add 1 to the compressed length (for the character itself).
- If the count is greater than 1, add the number of digits in the count to the compressed length.
- If the compressed length is not smaller than the original length, return the original string.
- Second pass: Create the compressed string using the same logic as the first approach.
- Return the compressed string.
Time Complexity:
where n is the length of the input string. We need to iterate through each character once in each pass, so it's still O(n).
Space Complexity:
In the worst case, the compressed string could be as long as the original string.
Pseudocode
1234567891011121314151617181920212223242526function compress(s): if s is empty: return s result = "" count = 1 for i from 1 to s.length - 1: if s[i] == s[i-1]: count++ else: result += s[i-1] if count > 1: result += count.toString() count = 1 // Handle the last character result += s[s.length - 1] if count > 1: result += count.toString() // Return the shorter string if result.length < s.length: return result else: return sString Problems
Learning Objective
Understand different approaches to solve the file compression system problem and analyze their efficiency.
Solution Approaches
Approach 1: Two-Pointer Approach
We can use a two-pointer approach to iterate through the string and count consecutive characters. We'll maintain a pointer to the current character and another to track the count of consecutive occurrences.
Input: "aabcccccaaa"
Count 'a': 2, Add "a2" to result
Count 'b': 1, Add "b" to result
Count 'c': 5, Add "c5" to result
Count 'a': 3, Add "a3" to result
Final result: "a2bc5a3"
Algorithm:
- Initialize an empty result string.
- Initialize a counter to 1 (to count consecutive characters).
- Iterate through the string from the second character to the end.
- If the current character is the same as the previous one, increment the counter.
- If the current character is different from the previous one, append the previous character to the result.
- If the counter is greater than 1, also append the counter to the result.
- Reset the counter to 1 and continue.
- After the loop, handle the last character and its count.
- Compare the length of the compressed string with the original string and return the shorter one.
Approach 2: Two-Pass Approach
To optimize the solution, we can first calculate the length of the compressed string without actually creating it. If the compressed length is not smaller than the original length, we can return the original string immediately. Otherwise, we perform the compression in a second pass.
Algorithm:
- First pass: Calculate the length of the compressed string.
- Initialize a counter to 1 and a compressed length to 0.
- Iterate through the string and count consecutive characters.
- For each group of consecutive characters, add 1 to the compressed length (for the character itself).
- If the count is greater than 1, add the number of digits in the count to the compressed length.
- If the compressed length is not smaller than the original length, return the original string.
- Second pass: Create the compressed string using the same logic as the first approach.
- Return the compressed string.
Complexity Analysis
Two-Pointer Approach Approach
Time Complexity
where n is the length of the input string. We need to iterate through each character once.
Space Complexity
In the worst case, the compressed string could be as long as the original string (if there are no repeated characters).
Two-Pass Approach Approach
Time Complexity
where n is the length of the input string. We need to iterate through each character once in each pass, so it's still O(n).
Space Complexity
In the worst case, the compressed string could be as long as the original string.
Comparison:
Both approaches have the same time and space complexity. The two-pass approach has the advantage of avoiding unnecessary string creation if the compressed string would not be smaller than the original. This can be more efficient in cases where compression doesn't save space. However, it requires iterating through the string twice, which might be slightly slower for strings that do benefit from compression.
Pseudocode
Two-Pointer Approach Approach
1234567891011121314151617181920212223242526function compress(s): if s is empty: return s result = "" count = 1 for i from 1 to s.length - 1: if s[i] == s[i-1]: count++ else: result += s[i-1] if count > 1: result += count.toString() count = 1 // Handle the last character result += s[s.length - 1] if count > 1: result += count.toString() // Return the shorter string if result.length < s.length: return result else: return sTwo-Pass Approach Approach
123456789101112131415161718192021222324252627282930313233343536373839404142434445function compress(s): if s is empty: return s // First pass: Calculate compressed length compressedLength = 0 count = 1 for i from 1 to s.length - 1: if s[i] == s[i-1]: count++ else: compressedLength += 1 // for the character if count > 1: compressedLength += count.toString().length // for the count count = 1 // Handle the last character compressedLength += 1 if count > 1: compressedLength += count.toString().length // If compression doesn't save space, return original if compressedLength >= s.length: return s // Second pass: Create compressed string result = "" count = 1 for i from 1 to s.length - 1: if s[i] == s[i-1]: count++ else: result += s[i-1] if count > 1: result += count.toString() count = 1 // Handle the last character result += s[s.length - 1] if count > 1: result += count.toString() return result