Compress a String in Java
Problem
Run-length encoding stores a run of identical characters as the character plus how many times it repeats, so aaab becomes a3b1.
Given a string, compress it by writing each character followed by the length of its consecutive run.
Java Program
public class CompressString {
public static void main(String[] args) {
String text = "aaabccdddd";
StringBuilder compressed = new StringBuilder();
int i = 0;
while (i < text.length()) {
char c = text.charAt(i);
int run = 0;
while (i < text.length() && text.charAt(i) == c) { // measure the run of this character
run++;
i++;
}
compressed.append(c).append(run);
}
System.out.println("Original: " + text);
System.out.println("Compressed: " + compressed);
}
}Output
Core Logic
Walking the string once, an inner loop measures how far each run of the same character extends, then records the character and its run length.
- 1
cholds the character that starts the current run. - 2The inner
whileadvancesiand incrementsrunfor as long as the characters matchc. - 3When the run ends,
candrunare appended tocompressed. - 4The outer loop continues from where the inner loop stopped, so every character is read exactly once.
aaa → a3, b → b1, cc → c2, dddd → d4.Key Point: Because the inner loop moves i forward, the two nested loops still take one linear pass — nested loops don't automatically mean O(n²).
Why: Each character is read once, and the compressed output can be up to twice the input length when nothing repeats.
Key Concepts
Approach 2: Skip Single Counts, Keep the Shorter Result
public class CompressStringShorterOnly {
public static void main(String[] args) {
System.out.println(compress("aaabccdddd"));
System.out.println(compress("abcd")); // compressing would make it longer
}
static String compress(String text) {
StringBuilder out = new StringBuilder();
for (int i = 0; i < text.length(); ) {
int start = i;
while (i < text.length() && text.charAt(i) == text.charAt(start)) i++;
int run = i - start;
out.append(text.charAt(start));
if (run > 1) out.append(run); // single characters stay as they are
}
return out.length() < text.length() ? out.toString() : text; // keep whichever is shorter
}
}
Output
Core Logic
A practical variant writes counts only for runs longer than one, and falls back to the original text when compression wouldn't actually save space.
- 1
startmarks the beginning of a run, andiadvances past it. - 2
run = i - startgives the run length. - 3The count is appended only when
run > 1, sobstaysb. - 4The method returns whichever of the compressed and original strings is shorter.
aaabccdddd becomes a3bc2d4 (7 characters instead of 10), while abcd is returned unchanged.Key Point: Dropping the 1s makes the output ambiguous to decode when the text itself contains digits — fine for display, but not for a reversible format.
Why: One pass builds the output, and the builder holds at most about n characters.
Key Concepts
Interview Questions
When does run-length encoding make a string longer?
When characters rarely repeat. "abcd" becomes "a1b1c1d1", twice the original length, which is why practical versions keep whichever result is shorter.
How would you decompress the result?
Read a character, then read all the digits that follow it as a count, and append the character that many times. Counts above 9 need several digits, so read until the next non-digit.