String Compression
Java coding interview problem for String Coding: String Compression.
String Compression is one of the most frequently asked Java String interview problems.
It appears in coding interviews because it tests multiple programming concepts, including:
- String Manipulation
- Character Traversal
- Two Pointers
- StringBuilder
- Run-Length Encoding (RLE)
- Space Optimization
- Time Complexity Analysis
Interviewers often ask several variations of this problem, such as:
- Compress a string using character counts.
- Compress in-place without extra space.
- Return the compressed string only if it is shorter.
- Implement Run-Length Encoding.
- Decompress the compressed string.
Understanding multiple approaches prepares you for all these interview variations.
Problem Statement
Given a string consisting of repeated characters, compress it by replacing consecutive repeated characters with the character followed by its count.
If the compressed string is not shorter than the original string, return the original string.
Example 1
Input
aaabbcccc
Output
a3b2c4
Example 2
Input
abcd
Output
abcd
Compression would produce
a1b1c1d1
which is longer than the original string.
Example 3
Input
aabcccccaaa
Output
a2b1c5a3
Example 4
Input
zzzzzz
Output
z6
What is String Compression?
String Compression reduces the size of a string by replacing repeated consecutive characters with:
Character + Count
Example
Original
aaabbb
Compressed
a3b3
Another Example
Original
xxxxxyyyzz
Compressed
x5y3z2
Notice
Only consecutive repeated characters are grouped together.
Why is this Question Asked in Interviews?
This problem evaluates whether candidates understand:
- Character Traversal
- Two Pointer Technique
- StringBuilder
- Counting Consecutive Elements
- Space Optimization
- Edge Cases
It also forms the basis of several advanced compression algorithms.
Examples include:
- Run-Length Encoding (RLE)
- Huffman Coding
- LZW Compression
- ZIP File Compression Concepts
Real-World Applications
String compression is used in many real-world systems.
File Compression
ZIP utilities reduce storage by compressing repeated patterns.
Data Transmission
Compressed data travels faster across networks.
Image Compression
Image formats reduce repeated pixel information.
Log Compression
Servers compress repetitive log entries.
DNA Sequence Storage
Repeated DNA sequences can be compressed to save storage.
Understanding String Compression
Suppose we have
aaabbcccc
Group characters
aaa
bb
cccc
Replace each group with
Character
+
Count
Result
a3b2c4
Another Example
Original
aaaaabccccdd
Compression
a5b1c4d2
Run-Length Encoding (RLE)
The most common compression technique for interview questions is Run-Length Encoding (RLE).
It stores
Character
+
Frequency
instead of repeating characters.
Example
Original
AAAAA
Encoded
A5
Example
Original
BBBBCCCCAAA
Encoded
B4C4A3
Mathematical Concept
Consider
aaabbcccc
Count
a
↓
3
Count
b
↓
2
Count
c
↓
4
Combine
a3b2c4
Visual Representation
Original
aaabbcccc
Grouping
aaa
bb
cccc
Compression
a3
b2
c4
Final
a3b2c4
Dry Run
Input
aaabbcccc
Step 1
Read
aaa
Output
a3
Step 2
Read
bb
Output
a3b2
Step 3
Read
cccc
Output
a3b2c4
Final Result
a3b2c4
Approach 1 — Using StringBuilder (Recommended)
This is the most popular interview solution.
The idea is simple.
- Traverse the string.
- Count consecutive repeated characters.
- Append the character and its count.
- Return the compressed string only if it is shorter.
Algorithm
- Create a
StringBuilder. - Traverse the string.
- Count repeated characters.
- Append character and count.
- Compare compressed length with original length.
- Return the shorter string.
Java Program
public class StringCompression {
public static String compress(String text) {
if (text == null || text.isEmpty()) {
return text;
}
StringBuilder compressed = new StringBuilder();
int count = 1;
for (int i = 1; i <= text.length(); i++) {
if (i < text.length()
&& text.charAt(i) == text.charAt(i - 1)) {
count++;
} else {
compressed.append(text.charAt(i - 1));
compressed.append(count);
count = 1;
}
}
return compressed.length() < text.length()
? compressed.toString()
: text;
}
public static void main(String[] args) {
System.out.println(
compress("aaabbcccc"));
System.out.println(
compress("abcd"));
System.out.println(
compress("aabcccccaaa"));
}
}
Output
a3b2c4
abcd
a2b1c5a3
Step-by-Step Code Explanation
Handle empty input.
if (text == null || text.isEmpty())
Create the result.
StringBuilder compressed =
new StringBuilder();
Initialize the counter.
int count = 1;
Compare adjacent characters.
text.charAt(i)
==
text.charAt(i - 1)
If equal,
increment the count.
Otherwise
append
compressed.append(character);
compressed.append(count);
Finally
return compressed.length() < text.length()
? compressed.toString()
: text;
This avoids returning a larger string.
Dry Run of StringBuilder Approach
Input
aabcccccaaa
| Character Group | Count | Compressed String |
|---|---|---|
| aa | 2 | a2 |
| b | 1 | a2b1 |
| ccccc | 5 | a2b1c5 |
| aaa | 3 | a2b1c5a3 |
Final Output
a2b1c5a3
Advantages
- Most common interview solution.
- Easy to implement.
- Uses efficient mutable strings.
- Linear time complexity.
- Excellent readability.
Drawbacks
- Requires additional memory.
- Not in-place.
- Appends counts even for single characters.
Approach 2 — Using Two Pointers
The Two Pointer technique is another elegant interview solution.
Instead of repeatedly comparing every character,
maintain two pointers.
- One pointer marks the beginning of a group.
- Another pointer scans forward until the group ends.
Visualization
Input
aaabbcccc
a a a b b c c c c
↑
L
↑
R
Move the right pointer.
a a a b b c c c c
↑
R
Count
3
Append
a3
Repeat for every group.
Algorithm
- Initialize two pointers.
- Move the right pointer while characters match.
- Append character and count.
- Move the left pointer to the next group.
- Continue until the end.
Java Program
public class StringCompressionTwoPointers {
public static String compress(String text) {
if (text == null || text.isEmpty()) {
return text;
}
StringBuilder result = new StringBuilder();
int left = 0;
while (left < text.length()) {
int right = left;
while (right < text.length()
&& text.charAt(right) == text.charAt(left)) {
right++;
}
result.append(text.charAt(left));
result.append(right - left);
left = right;
}
return result.length() < text.length()
? result.toString()
: text;
}
public static void main(String[] args) {
System.out.println(
compress("aaabbcccc"));
}
}
Output
a3b2c4
Step-by-Step Code Explanation
Initialize
int left = 0;
The left pointer marks the beginning of the current group.
Move the right pointer.
while (right < text.length()
&& text.charAt(right)
== text.charAt(left))
This counts all consecutive occurrences.
Append
result.append(text.charAt(left));
result.append(right - left);
The count is
right - left
Move to the next group.
left = right;
Repeat until the string ends.
Time & Space Complexity
| Approach | Time | Extra Space |
|---|---|---|
| StringBuilder | O(n) | O(n) |
| Two Pointers | O(n) | O(n) |
Where:
- n = length of the input string.
Comparison of Approaches
| Feature | StringBuilder | Two Pointers |
|---|---|---|
| Interview Friendly | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| Easy to Understand | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐ |
| Performance | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| Extra Space | O(n) | O(n) |
Advantages
- Both approaches run in linear time.
- Both are simple and easy to explain during interviews.
- The Two Pointer approach demonstrates an important problem-solving technique frequently used in DSA.
Drawbacks
- Both require additional space for the compressed string.
- Neither modifies the original string in place.
- Interviewers may ask for an in-place compression solution (such as LeetCode 443), which we'll cover next.
In Part 2, we'll cover:
- Approach 3 – In-Place Compression (LeetCode 443)
- Approach 4 – Using Character Frequency (When Applicable)
- Approach 5 – Run-Length Encoding (RLE)
- Compression vs Decompression
- Unicode Considerations
- Comparison of All Approaches
- Common Interview Mistakes
- Edge Cases
- Interview Follow-up Questions
- Related Problems
- Key Takeaways
- Frequently Asked Interview Questions
- Interview Tips
Approach 3 — In-Place Compression (LeetCode 443)
A popular interview variation asks you to compress the characters in-place without creating another string.
Instead of returning a new string, modify the character array and return the new length.
Example
Input
[a,a,b,b,c,c,c]
Output
[a,2,b,2,c,3]
New Length
6
Why In-Place?
- No additional array
- Constant extra space
- Frequently asked in FAANG interviews
- Official LeetCode 443 solution
Algorithm
- Maintain two pointers.
- Read one group at a time.
- Write the character.
- Write the frequency if greater than 1.
- Return the final write position.
Visualization
Input
a a b b c c c
↑
Read
Write
a 2
Continue
b 2
Continue
c 3
Final Array
a 2 b 2 c 3
Java Program
public class StringCompressionInPlace {
public static int compress(char[] chars) {
int write = 0;
int read = 0;
while (read < chars.length) {
char current = chars[read];
int count = 0;
while (read < chars.length &&
chars[read] == current) {
read++;
count++;
}
chars[write++] = current;
if (count > 1) {
String frequency =
String.valueOf(count);
for (char c : frequency.toCharArray()) {
chars[write++] = c;
}
}
}
return write;
}
public static void main(String[] args) {
char[] chars = {
'a','a','b','b','c','c','c'
};
int length = compress(chars);
System.out.println(length);
for (int i = 0; i < length; i++) {
System.out.print(chars[i]);
}
}
}
Output
6
a2b2c3
Advantages
- Constant extra space.
- Official interview solution.
- Excellent for array manipulation.
Drawbacks
- Slightly harder to understand.
- Works on character arrays instead of immutable strings.
Approach 4 — Using Character Frequency (When Applicable)
Sometimes interviewers intentionally modify the problem.
Instead of compressing consecutive characters,
they ask for the frequency of every character.
Example
banana
Output
b1a3n2
Notice
This is NOT String Compression.
It is simply frequency counting.
Algorithm
- Count every character.
- Store frequencies.
- Print each character once.
Java Program
import java.util.LinkedHashMap;
import java.util.Map;
public class CharacterFrequency {
public static void frequency(String text) {
Map<Character, Integer> map =
new LinkedHashMap<>();
for (char ch : text.toCharArray()) {
map.put(ch,
map.getOrDefault(ch, 0) + 1);
}
for (Map.Entry<Character, Integer> entry :
map.entrySet()) {
System.out.print(
entry.getKey() +
String.valueOf(entry.getValue()));
}
}
public static void main(String[] args) {
frequency("banana");
}
}
Output
b1a3n2
Important Difference
Compression
aaabbbaa
↓
a3b3a2
Frequency
aaabbbaa
↓
a5b3
Compression preserves the sequence.
Frequency counting ignores positions.
Approach 5 — Run-Length Encoding (RLE)
Run-Length Encoding (RLE) is the foundation of most interview solutions.
Instead of storing every character,
store
Character
+
Count
Example
Original
AAAAAAAA
Compressed
A8
Another Example
AAAABBBCCDAA
↓
A4B3C2D1A2
Java Program
public class RunLengthEncoding {
public static String encode(String text) {
if (text.isEmpty()) {
return "";
}
StringBuilder result =
new StringBuilder();
int count = 1;
for (int i = 1; i <= text.length(); i++) {
if (i < text.length() &&
text.charAt(i)
== text.charAt(i - 1)) {
count++;
} else {
result.append(text.charAt(i - 1));
result.append(count);
count = 1;
}
}
return result.toString();
}
public static void main(String[] args) {
System.out.println(
encode("AAAABBBCCDAA"));
}
}
Output
A4B3C2D1A2
Advantages
- Simple implementation.
- Excellent interview example.
- Basis of many compression algorithms.
Drawbacks
- Inefficient for random strings.
- May increase output size.
Compression vs Decompression
Compression
aaaaabbb
↓
a5b3
Decompression
a5b3
↓
aaaaabbb
Compression reduces storage.
Decompression reconstructs the original data.
Unicode Considerations
Java supports Unicode.
Examples
こんにちは
नमस्ते
😊😊😊😊
The algorithms work correctly for general Java strings.
For supplementary Unicode characters (such as many emoji), prefer iterating over Unicode code points instead of individual char values.
Edge Cases
| Input | Compressed Output |
|---|---|
"" |
"" |
"a" |
a (or a1, depending on the requirement) |
"aaaa" |
a4 |
"abcd" |
abcd |
"aabcccccaaa" |
a2b1c5a3 |
null |
Handle appropriately based on application requirements |
Time & Space Complexity
| Approach | Time | Extra Space |
|---|---|---|
| StringBuilder | O(n) | O(n) |
| Two Pointers | O(n) | O(n) |
| In-Place Compression | O(n) | O(1) |
| Character Frequency | O(n) | O(k) |
| Run-Length Encoding | O(n) | O(n) |
Where:
- n = length of the string
- k = number of distinct characters
Comparison of All Approaches
| Approach | Interview Friendly | Performance | Best Use Case |
|---|---|---|---|
| StringBuilder | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | General interviews |
| Two Pointers | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | Traversal problems |
| In-Place Compression | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | LeetCode 443 / FAANG |
| Character Frequency | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ | Frequency analysis |
| Run-Length Encoding | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ | Compression fundamentals |
Common Interview Mistakes
Mistake 1
Compressing non-consecutive characters.
Wrong
banana
↓
b1a3n2
That is frequency counting.
Correct Compression
banana
↓
b1a1n1a1n1a1
Mistake 2
Returning the compressed string even when it is longer.
Example
abcd
↓
a1b1c1d1
Return
abcd
instead.
Mistake 3
Forgetting the final character group.
Many candidates process a group only when the character changes.
Always remember to append the last group.
Mistake 4
Using immutable strings repeatedly.
Prefer
StringBuilder
instead of repeated string concatenation inside loops.
Mistake 5
Confusing String Compression with Character Frequency.
These are different interview questions.
Interview Follow-up Questions
Q1. Can you compress the string in-place?
Q2. Why is StringBuilder preferred over String?
Q3. What is Run-Length Encoding?
Q4. When does compression increase the string size?
Q5. Can you decompress the compressed string?
Q6. How would you support Unicode?
Q7. How would you compress binary data?
Q8. Can you perform compression using recursion?
Q9. What is the complexity of your solution?
Q10. What compression algorithms are used in ZIP files?
Related Problems
- LeetCode 443 – String Compression
- Remove Duplicate Characters
- Count Character Frequency
- String Rotation
- Reverse String
- Encode and Decode Strings
- Implement Run-Length Encoding
- Huffman Coding (Concept)
Key Takeaways
- String Compression replaces consecutive repeated characters with the character followed by its count.
- StringBuilder is the most common interview solution because it is efficient and easy to implement.
- The Two Pointer technique is a clean way to process consecutive character groups.
- In-Place Compression is the optimal solution for LeetCode 443 and uses O(1) extra space.
- Run-Length Encoding (RLE) is the underlying concept behind most interview solutions.
- Character Frequency counting is a different problem because it ignores the order of characters.
Frequently Asked Interview Questions
Q1. Which solution is best for interviews?
The StringBuilder solution is the most common because it is simple, efficient, and easy to explain.
Q2. Which solution is best for LeetCode 443?
The In-Place Compression approach is the preferred solution because it modifies the array directly using constant extra space.
Q3. Why use StringBuilder?
String objects are immutable.
StringBuilder avoids creating multiple temporary objects while building the compressed result.
Q4. What is Run-Length Encoding?
Run-Length Encoding (RLE) stores repeated consecutive characters as:
Character + Count
Example
AAAAABB
↓
A5B2
Q5. Does compression always reduce the size?
No.
For example,
abcd
↓
a1b1c1d1
is longer than the original string.
Many interview problems therefore require returning the original string if the compressed version is not shorter.
Interview Tip
If an interviewer asks:
"Compress a string."
Start with the StringBuilder solution because it is the standard interview answer.
Then discuss progressively advanced approaches:
- StringBuilder (most common)
- Two Pointers (efficient traversal)
- In-Place Compression (LeetCode 443)
- Run-Length Encoding (compression concept)
- Character Frequency (clarify that it solves a different problem)
Before coding, ask clarifying questions such as:
- Should I return the original string if compression is not beneficial?
- Are counts of 1 required in the output?
- Is the compression required to be performed in place?
- Can the input contain Unicode characters?
- Can the input be empty or
null?
Clarifying these requirements first demonstrates strong communication skills and leads to a more robust interview solution.