Consecutive Character Encoder ā Problem Statement & Solution Guide
Problem Description
Given a string s consisting of lowercase English letters, implement a function to compress it using a custom encoding where sequences of the same letters are replaced by the letter followed by the count of its consecutive occurrences, except when the count is 1, in which case only the letter is output, and sequences of exactly two identical letters are left uncompressed.
Examples
Input
aabcccccaaa
Output
a1b1c5a3a
Explanation: Step-by-step: 1. Initialize an empty string result and a counter count to 1. 2. Iterate through the input string s. 3. If the current character is the same as the previous one, increment the count. 4. If the current character is different from the previous one, append the previous character and count to the result and reset the count to 1. 5. If the count is greater than 1, append the current character and count to the result. 6. Return the result.
Input
a1b1c1d1e1f1
Output
a1b1c1d1e1f1
Explanation: Step-by-step: 1. The input string is already in the desired format, so no compression is needed. 2. Return the input string as the result.
Constraints
- The input string will only contain lowercase English letters.
- The length of the input string will be between 97 and 6787 characters (inclusive).
Optimal Approach & Strategy
A more efficient solution involves iterating over the string once and using a counter to keep track of consecutive occurrences of each letter. This approach would have a linear time complexity.
Brute Force Approach
One naive approach is to use nested loops to compare each character with the next ones and build the compressed string. This would result in a time complexity of O(nĀ²). Another brute-force method could involve dividing the string into substrings and checking for compressible sequences.
Verified Code Solutions
class Solution {
public String compress(String s) {
if (s == null || s.length() == 0) return s;
StringBuilder result = new StringBuilder(s.charAt(0) + '1');
int count = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i-1)) {
count++;
} else {
if (count > 1) {
result.append(s.charAt(i-1)).append(count);
}
result.append(s.charAt(i));
count = 1;
}
}
if (count > 1) {
result.append(s.charAt(s.length()-1)).append(count);
}
return result.toString();
}
}def compress(s: str) -> str:
if not s: return s
result = s[0] + '1'
count = 1
for i in range(1, len(s)):
if s[i] == s[i-1]:
count += 1
else:
if count > 1:
result += s[i-1] + str(count)
result += s[i]
count = 1
if count > 1:
result += s[-1] + str(count)
return resultAsked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.