In this tutorial, I will demonstrate how to implement string compression using character counts in Java. This is a common string-based coding interview question that helps you understand string traversal, consecutive character counting, and StringBuilder.
String compression is a technique that represents consecutive repeated characters using the character followed by the number of times it appears continuously.
For example, the string "aaabbcccc" can be compressed into "a3b2c4". Instead of storing every repeated character individually, the program stores each group of consecutive characters along with its count.
This technique is also known as run-length encoding (RLE). It is a simple form of data compression and frequently appears in programming exercises and technical interviews.
In this tutorial, you will learn how to implement string compression using a loop and StringBuilder, how to return the original string when compression does not reduce its length, and how to handle important edge cases.
1. Problem Statement
Write a Java program to compress a string by replacing consecutive repeated characters with the character followed by its count.
Each character must be followed by the number of consecutive times it appears, even when that number is one.
Example 1
Input: aaabbcccc Output: a3b2c4
Explanation:
- The character 'a' appears three times consecutively.
- The character 'b' appears twice consecutively.
- The character 'c' appears four times consecutively.
Therefore, the compressed string is "a3b2c4".
Example 2
Input: aabcccccaaa Output: a2b1c5a3
Notice that the character 'a' appears in two separate groups. The program counts each consecutive group independently.
Example 3
Input: abcd Output: a1b1c1d1
Even though every character appears only once, the basic compression algorithm includes a count of 1 for each character.
2. Understanding String Compression Using Character Counts
The idea is to scan the string from left to right and count how many consecutive times the current character appears.
Whenever the next character differs from the current character, the program appends the current character and its count to the compressed result.
Consider the string:
aaabbcccc
The algorithm identifies three groups:
| Group | Character | Count | Compressed Representation |
|---|---|---|---|
| aaa | a | 3 | a3 |
| bb | b | 2 | b2 |
| cccc | c | 4 | c4 |
Combining these representations produces:
a3b2c4
3. Method 1: String Compression Using StringBuilder
The most practical approach is to use a loop to count consecutive characters and a StringBuilder to construct the compressed string.
StringBuilder is suitable for this problem because Java String objects are immutable. Repeatedly concatenating String objects can create unnecessary intermediate objects.
With StringBuilder, you can append characters and counts efficiently.
Algorithm
- Check whether the input string is null or empty.
- Create a StringBuilder to store the compressed result.
- Initialize a counter to 1.
- Start from the second character and compare it with the previous character.
- If both characters are equal, increment the counter.
- If they differ, append the previous character and its count, then reset the counter.
- After the loop, append the final character group.
- Return the compressed string.
Java Program Using StringBuilder
public class StringCompression {
/**
* Compresses consecutive repeated characters
* using run-length encoding.
*
* Example: aaabbcccc becomes a3b2c4
*
* @param str input string
* @return compressed string
*/
public static String compressString(String str) {
if (str == null || str.isEmpty()) {
return str;
}
StringBuilder compressed = new StringBuilder();
int count = 1;
for (int i = 1; i < str.length(); i++) {
// Check if current and previous characters match
if (str.charAt(i) == str.charAt(i - 1)) {
count++;
} else {
// Append completed character group
compressed.append(str.charAt(i - 1));
compressed.append(count);
// Start counting the new character
count = 1;
}
}
// Append the final character group
compressed.append(str.charAt(str.length() - 1));
compressed.append(count);
return compressed.toString();
}
public static void main(String[] args) {
String str = "aaabbcccc";
String result = compressString(str);
System.out.println("Original String: " + str);
System.out.println("Compressed String: " + result);
}
}Output
Original String: aaabbcccc Compressed String: a3b2c4
This implementation processes each character once and produces the compressed representation using consecutive character counts.
4. Step-by-Step Explanation of the Java Program
Step 1: Check for Null or Empty Input
if (str == null || str.isEmpty()) {
return str;
}If the input is null or empty, the method returns it directly.
This prevents the program from accessing an invalid character index.
Step 2: Create a StringBuilder
StringBuilder compressed = new StringBuilder();The StringBuilder stores the compressed result.
As the program processes the input, it appends each completed character group.
Step 3: Initialize the Counter
int count = 1;The counter starts at 1 because the first character has already been included in the current group.
Step 4: Traverse the String
for (int i = 1; i < str.length(); i++) {The loop starts at index 1 so that each character can be compared with the previous character.
Step 5: Count Consecutive Characters
if (str.charAt(i) == str.charAt(i - 1)) {
count++;
}If the current character matches the previous character, the program increments the count.
For example, when processing "aaa", the count increases from 1 to 3.
Step 6: Append a Completed Group
else {
compressed.append(str.charAt(i - 1));
compressed.append(count);
count = 1;
}When the current character differs from the previous character, the current group has ended.
The program appends the previous character followed by its count.
Then it resets the counter to 1 for the new group.
Step 7: Append the Final Group
compressed.append(str.charAt(str.length() - 1));
compressed.append(count);The loop appends a group only when it encounters a different character.
Therefore, the final group must be appended separately after the loop finishes.
Without these statements, the last group would be missing from the compressed result.
Step 8: Return the Compressed String
return compressed.toString();The toString() method converts the StringBuilder into the final compressed String.
5. Dry Run: String Compression Using Character Counts
Let's walk through the algorithm using the string:
aaabbcccc
The algorithm tracks consecutive characters and appends completed groups to the result.
| Index | Current Character | Count After Processing | Compressed Result So Far |
|---|---|---|---|
| 0 | a | 1 | Empty |
| 1 | a | 2 | Empty |
| 2 | a | 3 | Empty |
| 3 | b | 1 | a3 |
| 4 | b | 2 | a3 |
| 5 | c | 1 | a3b2 |
| 6 | c | 2 | a3b2 |
| 7 | c | 3 | a3b2 |
| 8 | c | 4 | a3b2 |
| After loop | Final group c | 4 | a3b2c4 |
The final compressed string is:
a3b2c4
6. Method 2: Return the Original String When Compression Is Not Shorter
In some coding interviews, the requirement is slightly different.
The program must return the compressed string only when it is shorter than the original string.
If compression does not reduce the string length, the program should return the original string.
For example:
Input: abcd Basic Compression: a1b1c1d1 Expected Result: abcd
The compressed representation is longer than the original, so returning the original string is preferable under this requirement.
Java Program
public class StringCompressionOptimized {
public static String compressString(String str) {
if (str == null || str.isEmpty()) {
return str;
}
StringBuilder compressed = new StringBuilder();
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == str.charAt(i - 1)) {
count++;
} else {
compressed.append(str.charAt(i - 1));
compressed.append(count);
count = 1;
}
}
// Append the final character group
compressed.append(str.charAt(str.length() - 1));
compressed.append(count);
// Return compressed string only if it is shorter
return compressed.length() < str.length()
? compressed.toString()
: str;
}
public static void main(String[] args) {
String str1 = "aaabbcccc";
String str2 = "abcd";
String str3 = "aabb";
System.out.println(str1 + " -> "
+ compressString(str1));
System.out.println(str2 + " -> "
+ compressString(str2));
System.out.println(str3 + " -> "
+ compressString(str3));
}
}Output
aaabbcccc -> a3b2c4 abcd -> abcd aabb -> aabb
How This Approach Works
The compression logic remains the same as in Method 1.
The only difference is the final comparison:
return compressed.length() < str.length()
? compressed.toString()
: str;If the compressed representation is shorter, the program returns it.
Otherwise, it returns the original string.
This variation is useful for coding interview problems that explicitly require compression to reduce the output length.
7. Method 3: String Compression Using Two Pointers
You can also implement string compression using two pointers.
One pointer identifies the beginning of the current character group, while the other pointer moves forward to locate the end of that group.
Java Program Using Two Pointers
public class StringCompressionTwoPointers {
public static String compressString(String str) {
if (str == null || str.isEmpty()) {
return str;
}
StringBuilder compressed = new StringBuilder();
int left = 0;
while (left < str.length()) {
int right = left;
// Find the end of the current character group
while (right < str.length()
&& str.charAt(right) == str.charAt(left)) {
right++;
}
// Calculate consecutive character count
int count = right - left;
compressed.append(str.charAt(left));
compressed.append(count);
// Move to the next character group
left = right;
}
return compressed.toString();
}
public static void main(String[] args) {
String str = "aabcccccaaa";
String result = compressString(str);
System.out.println("Original String: " + str);
System.out.println("Compressed String: " + result);
}
}Output
Original String: aabcccccaaa Compressed String: a2b1c5a3
How the Two-Pointer Approach Works
The left pointer marks the beginning of a group of identical consecutive characters.
The right pointer moves forward until it reaches a different character or the end of the string.
The number of consecutive characters is:
int count = right - left;After appending the character and its count, the program moves left to right and processes the next group.
Each character is examined a constant number of times, so the algorithm runs in linear time.
8. Time and Space Complexity
All three implementations process the input string in a single forward traversal.
| Approach | Time Complexity | Space Complexity | Behavior |
|---|---|---|---|
| StringBuilder with counter | O(n) | O(n) | Always produces character counts |
| Return shorter representation | O(n) | O(n) | Returns original if not shorter |
| Two pointers | O(n) | O(n) | Processes consecutive groups |
Here, n represents the length of the input string in UTF-16 code units.
Time Complexity: O(n)
Each character is processed a constant number of times.
Therefore, the time complexity is O(n).
Space Complexity: O(n)
The StringBuilder stores the compressed representation.
In the worst case, the compressed representation can be longer than the original string because every character may require an additional count.
For example:
Original: abcd Compressed: a1b1c1d1
The compressed output still has a length proportional to the input length, so the space complexity is O(n).
9. Handling Important Edge Cases
Case 1: Empty String
Input: "" Output: ""
The program returns an empty string.
Case 2: Single Character
Input: "a" Basic Compression: a1
Under the shorter-result variation, the program returns "a" because it is shorter than "a1".
Case 3: All Characters Are Identical
Input: aaaaaa Output: a6
Case 4: No Consecutive Repeated Characters
Input: abcdef Basic Compression: a1b1c1d1e1f1
The basic algorithm always appends counts, so the compressed representation can be longer than the original string.
Case 5: Repeated Characters in Separate Groups
Input: aabbaa Output: a2b2a2
The two groups of 'a' characters are counted separately because they are not consecutive.
Case 6: Uppercase and Lowercase Letters
Input: AAaaBB Output: A2a2B2
Java treats uppercase and lowercase characters as different values.
Case 7: More Than Nine Consecutive Characters
Input: aaaaaaaaaaaa Output: a12
The program correctly handles multi-digit counts using StringBuilder.
Case 8: Null Input
The implementations in this tutorial return null when the input string is null.
This is a design choice. In some applications, you may prefer returning an empty string or throwing an exception.
10. Important Limitations of Basic Run-Length Encoding
The character-count format used in this tutorial is intended as a simple coding interview example.
There are two important limitations to understand.
Limitation 1: Characters That Are Digits
If input strings contain digits, a compressed result may become ambiguous when you attempt to decode it.
For example, a string containing the digit '1' can produce a representation that is difficult to distinguish from a character count without additional rules.
If reliable decompression is required, define an encoding format with separators or escaping.
Limitation 2: Unicode Characters
Java strings use UTF-16 encoding, and the charAt() method returns individual UTF-16 code units.
Some Unicode characters, including many emoji, require two UTF-16 code units.
Therefore, the implementations in this tutorial count Java char values rather than complete Unicode code points or user-perceived characters.
For applications requiring full Unicode character handling, adapt the algorithm to work with Unicode code points or grapheme clusters.
11. Common Mistakes to Avoid
Mistake 1: Forgetting the Final Character Group
The most common mistake is forgetting to append the final group after the loop.
The loop appends a group only when the next character differs from the previous character.
Therefore, the final group must be handled separately.
Mistake 2: Counting All Occurrences Instead of Consecutive Occurrences
String compression based on run-length encoding counts consecutive repeated characters.
For example:
Input: aabbaa Correct: a2b2a2 Incorrect: a4b2
The incorrect result combines separate groups of 'a' characters.
Mistake 3: Forgetting to Reset the Counter
Whenever the character changes, reset the counter to 1.
Otherwise, counts from previous groups may incorrectly carry over.
Mistake 4: Using Repeated String Concatenation
Repeatedly concatenating immutable String objects inside a loop can create unnecessary intermediate objects.
Use StringBuilder for efficient string construction.
Mistake 5: Assuming Compression Always Reduces Length
Run-length encoding does not guarantee a shorter result.
If the input contains few consecutive repeated characters, the encoded representation may be longer.
Use the shorter-result variation when your requirements specify that the original string should be returned if compression provides no benefit.
12. Frequently Asked Questions
Q1. What is string compression in Java?
String compression is the process of representing repeated character sequences in a shorter or more structured form. In run-length encoding, consecutive characters are represented by the character followed by its repetition count.
Q2. What is run-length encoding?
Run-length encoding is a basic compression technique that replaces consecutive repeated values with a representation of the value and its count.
Q3. How do I compress a string using character counts in Java?
Traverse the string, count consecutive occurrences of each character, and append the character and count to a StringBuilder.
Q4. What is the time complexity of string compression?
The time complexity is O(n), where n is the number of characters processed.
Q5. Why is StringBuilder used for string compression?
StringBuilder allows efficient appending of characters and counts without repeatedly creating intermediate String objects.
Q6. Does string compression always reduce the length?
No. If the input contains few repeated characters, the compressed representation may be longer than the original string.
Q7. Can string compression handle multi-digit counts?
Yes. For example, twelve consecutive 'a' characters are represented as "a12".
Q8. Does the algorithm count nonconsecutive repeated characters together?
No. Run-length encoding counts each consecutive group separately.
Q9. Can string compression be implemented using two pointers?
Yes. One pointer marks the start of the current group, while another identifies the end of that group. The group length is the difference between their positions.
Q10. Which approach is best for Java coding interviews?
The StringBuilder approach with a character counter is usually the best starting point. It is simple, efficient, and easy to explain.
13. Conclusion
In this tutorial, you learned how to implement string compression using character counts in Java.
- StringBuilder with a counter: Compresses consecutive repeated characters in a single traversal.
- Return-original-if-not-shorter: Avoids returning an encoded string that is not shorter than the input.
- Two-pointer approach: Processes consecutive character groups using start and end indexes.
For Java coding interviews, I recommend practicing the StringBuilder with character counting approach first. It demonstrates string traversal, condition checking, and efficient string construction.
Once you understand the basic algorithm, practice the shorter-result variation because interviewers sometimes add that requirement.
The same concepts are useful in problems involving consecutive character counting, run-length encoding, string decoding, and compression algorithms.
14. Official Java Documentation
For additional information about the Java APIs used in this tutorial, refer to the official Oracle documentation:
- Java String Class — Documentation for
charAt(),length(), andisEmpty(). - Java StringBuilder Class — Documentation for
append(),length(), andtoString(). - Java Character Class — Documentation for character values and Unicode-related operations.
- Java Language Specification: Lexical Structure — Information about Java characters and Unicode processing.
Continue Learning with Java Guides
Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.
By Ramesh Fadatare - Udemy Instructor Partner
Comments
Post a Comment
Leave Comment