⌨️Java CodingIntermediate

Run-Length String Compression

📌 Definition:

Compress a string by replacing runs of the same character with the character and its count (e.g. "aaabbc" -> "a3b2c1"). Return the original if compression is not shorter.

📖 Detailed Explanation:

Scan once, counting consecutive equal characters; when the character changes, emit the previous character and its count. Build the result in a StringBuilder/array. Compare lengths at the end and return whichever is shorter. O(n).

💻 Solutions:

public static String compress(String s) {
    if (s.isEmpty()) return s;
    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)) count++;
        else { sb.append(s.charAt(i - 1)).append(count); count = 1; }
    }
    return sb.length() < s.length() ? sb.toString() : s;
}

function compress(s) {
  if (!s) return s;
  let out = '', count = 1;
  for (let i = 1; i <= s.length; i++) {
    if (i < s.length && s[i] === s[i - 1]) count++;
    else { out += s[i - 1] + count; count = 1; }
  }
  return out.length < s.length ? out : s;
}

def compress(s):
    if not s:
        return s
    out, count = [], 1
    for i in range(1, len(s) + 1):
        if i < len(s) and s[i] == s[i - 1]:
            count += 1
        else:
            out.append(s[i - 1] + str(count))
            count = 1
    result = ''.join(out)
    return result if len(result) < len(s) else s

🔑 Key Points:

Count consecutive runs in one pass
Emit char + count when the run ends
Return original if compressed is not shorter
Use a builder to avoid O(n^2) concatenation

🌍 Real-World Example:

Run-length encoding is a real compression scheme (bitmaps, simple image formats) and a common interview stand-in for stream aggregation.

🎯 Scenario-Based Interview Question:

For "abcdef" your function returns "a1b1c1d1e1f1", which is longer. What is the expected behavior?

‹ Previous

Longest Substring Without Repeating Characters

Next ›

Longest Common Prefix