String Compression or Run-Length Encoding problem and solution in Java and Python

Let’s go over the String Compression (Run-Length Encoding) problem — a classic array and string manipulation interview question that also tests in-place logic and counting patterns.

---

🧩 Problem: String Compression / Run-Length Encoding

Question:

Given a string (or array of characters), compress it so that:

• Consecutive repeating characters are replaced by the character + number of times it repeats.
• The compressed string should be returned (or written in-place for arrays).

---

Example 1:

Input:  "aaabbc"
Output: "a3b2c1" or "a3b2c"

Example 2:

Input:  "aabcccccaaa"
Output: "a2b1c5a3"

Example 3 (for array version, like in LeetCode 443):

Input:  ['a','a','b','b','c','c','c']
Output: ['a','2','b','2','c','3']

---

💡 Intuition

We need to count consecutive repeating characters and append:

character + count

This is exactly what Run-Length Encoding (RLE) does — it’s a basic form of data compression.

---

🧠 Approach 1 — Simple (Build New String)

🪜 Steps:

1. Initialize an empty string res

2. Loop through input string

3. For each group of repeating characters:

   • Count how many times it repeats
   • Append char + count to res

---

✅ Java Solution

class Solution {
    public String compress(String s) {
        if (s == null || s.length() == 0) return "";

        StringBuilder sb = new StringBuilder();
        int count = 1;

        for (int i = 1; i <= s.length(); i++) {
            if (i == s.length() || s.charAt(i) != s.charAt(i - 1)) {
                sb.append(s.charAt(i - 1));
                sb.append(count);
                count = 1;
            } else {
                count++;
            }
        }
        return sb.toString();
    }
}

Input: "aabcccccaaa" Output: "a2b1c5a3"

---

✅ Python Solution

def compress(s: str) -> str:
    if not s:
        return ""
    
    result = []
    count = 1

    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            count += 1
        else:
            result.append(s[i-1] + str(count))
            count = 1
    
    result.append(s[-1] + str(count))  # append last group
    return ''.join(result)

Input: "aaabbc" Output: "a3b2c1"

---

🧠 Approach 2 — In-Place Compression (for char arrays)

LeetCode style:

Given a character array chars, compress it in-place and return the new length.

---

✅ Java Solution

class Solution {
    public int compress(char[] chars) {
        int write = 0;
        int i = 0;

        while (i < chars.length) {
            char current = chars[i];
            int count = 0;

            while (i < chars.length && chars[i] == current) {
                i++;
                count++;
            }

            chars[write++] = current;

            if (count > 1) {
                for (char c : String.valueOf(count).toCharArray()) {
                    chars[write++] = c;
                }
            }
        }
        return write;
    }
}

---

✅ Python Solution

def compress(chars):
    write = 0
    i = 0
    
    while i < len(chars):
        current = chars[i]
        count = 0
        
        while i < len(chars) and chars[i] == current:
            i += 1
            count += 1
        
        chars[write] = current
        write += 1
        
        if count > 1:
            for c in str(count):
                chars[write] = c
                write += 1
    
    return write

---

⚖️ Complexity

Operation	Time	Space
Simple build version	O(n)	O(n)
In-place version	O(n)	O(1)

---

🌍 Real-World Analogy

This is how image compression or data transmission works at a basic level.

Example:

Original:  WWWWWWWWWBBBWW
Compressed: W9B3W2

This saves storage space — the same concept is used in ZIP, PNG, and video codecs but with more advanced encoding.

---

🧩 Edge Cases

Input	Output	Reason
"a"	"a1"	single char
"abc"	"a1b1c1" or "abc"	all unique
"aaaabbaa"	"a4b2a2"	mixed runs

---