String Compression (RLE)
Maintained by Vikas D, software engineer
You are given a string of lowercase letters. Walk through it and collapse every run of the same character that repeats back to back into the character followed by how many times it appeared in that run. When a character appears only once in a run, write the character alone with no number after it.
The catch is that this kind of encoding does not always save space. Short inputs with no real repetition can come out longer once the counts are stitched in. To guard against that, compare the length of the encoded result against the original.
If the encoded string is strictly shorter than the input, return the encoded string. If it is the same length or longer, return the original input untouched. The comparison is strict, so a tie counts as no improvement and the original wins.
Examples
Runs are aa, b, ccc, dddd, which encode to a2, b, c3, d4. The result has length 7 against the original 10, so the shorter encoded form is returned.
Every character is its own run of one, so encoding gives a1b1c1 at length 6. That is longer than the original length 3, so the input comes back unchanged.
Encoding produces a2b2, which is length 4, exactly equal to the input. Equal is not strictly shorter, so the original is returned.
Constraints
- 1 <= s.length <= 10^4
- s contains only lowercase English letters (a to z).
- A run count is written only when the run length is at least 2; a run of length 1 emits the character alone.
- Return the original string when the encoded form is not strictly shorter.
Visible test cases
- compressString("aabcccdddd") == "a2bc3d4"
- compressString("abc") == "abc"
- compressString("aabb") == "aabb"
- compressString("aaaaaaa") == "a7"
- compressString("aabbcc") == "aabbcc"
- compressString("aaabbbccc") == "a3b3c3"
Hints
Hint 1
Scan the string left to right and group together stretches where the current character matches the previous one. You only need to know where each group starts and how long it is.
Hint 2
Build the encoded output piece by piece: for each group append the character, then append the count only when the count is greater than one.
Hint 3
Once the encoded string is fully built, do a single length comparison. Return the encoded form only if its length is strictly less than the original, otherwise return the input as is.
Approaches
Brute force with repeated counting
Time O(n) · Space O(n)For each position, count how many of the same character follow it by re-scanning ahead, append the segment, and skip past the run. It works but the bookkeeping is clumsier than a clean single sweep.
- Start an index at 0 and an empty result accumulator.
- At each index, look forward and count consecutive matches of the current character.
- Append the character, and the count when it exceeds one, then advance the index past the counted run.
- After the full pass, compare lengths and return the encoded string only if it is strictly shorter, else the original.
Optimal single-pass two-pointer
Time O(n) · Space O(n)Use one pointer to mark the start of a run and a second to extend it while characters match. Each character is visited a constant number of times, and the result is assembled in one clean sweep.
- Initialize a start pointer i at 0 and an empty list or string for the output.
- Advance a second pointer j from i while s[j] equals s[i] to find the end of the run.
- The run length is j minus i; append s[i], and append that length as text only when it is at least 2.
- Set i to j and repeat until the string is consumed, then return the encoded form if its length is strictly less than the input, otherwise return the input.
Common mistakes
- Forgetting the strict-shorter rule and returning the encoded string when it ties the original length, as with "aabb" giving a2b2.
- Emitting a count of 1 for single characters, which both bloats the output and breaks the expected format.
- Comparing the wrong lengths, for example checking the count of runs instead of the actual character length of the encoded string.
- Building the result with repeated string concatenation in a tight loop without realizing it can be slow; collecting parts and joining once is cleaner for large inputs.
- Mishandling the final run because the loop stops before flushing the last group, which drops the trailing characters.
Follow-up variations
- Support decompression: given an encoded string, reconstruct the original.
- Handle multi-digit counts and arbitrary characters, including digits in the alphabet, which forces a delimiter or escaping scheme.
- Do the compression in place over a character array and return the new length, the harder variant interviewers often ask next.
- Make it case sensitive or extend it to full Unicode and discuss how the count representation changes.