How to Efficiently Compress Strings in Java: Interview‑Ready Solution

Recently a ridiculous interview story circulated where a candidate was asked to "hand‑tear B+ tree" and to recite map traversal code character by character, only to be told the result would be announced after six months. The post highlights two issues: some interviewers treat interviews as power‑plays with meaningless high‑pressure questions, and many companies have chaotic hiring processes that don’t actually intend to recruit.

The core technical question discussed is a classic string‑compression problem often seen in coding interviews. The task is to replace each run of identical characters with the character followed by the run length, e.g., aabcccccaaa becomes a2b1c5a3. The compression is only valid if the resulting string is shorter than the original.

Solution Overview

The implementation first estimates the length of the compressed string. If the estimated length is not smaller than the original, the original string is returned directly, avoiding unnecessary work. Otherwise, a StringBuilder is used to build the compressed result in a single pass.

Key points:

Count consecutive characters and append character+count to the builder.

Use a helper calcCompressedLen to compute the potential length, employing a digits function to handle multi‑digit counts.

Handle case‑sensitivity, spaces, and avoid trimming; treat the string as a sequence of UTF‑16 code units, but for proper Unicode handling you can iterate with codePoints() instead of char.

Avoid string concatenation inside loops; StringBuilder minimizes garbage collection overhead.

Reference Implementation (Java)

public class StringCompress {
    public static String compress(String s) {
        if (s == null || s.length() < 2) return s;
        int n = s.length();
        int targetLen = calcCompressedLen(s);
        if (targetLen >= n) return s; // not shorter
        StringBuilder sb = new StringBuilder(targetLen);
        int count = 1;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                count++;
            } else {
                sb.append(s.charAt(i - 1)).append(count);
                count = 1;
            }
        }
        sb.append(s.charAt(n - 1)).append(count);
        return sb.toString();
    }

    private static int calcCompressedLen(String s) {
        int n = s.length(), len = 0, count = 1;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                count++;
            } else {
                len += 1 + digits(count);
                count = 1;
            }
        }
        len += 1 + digits(count);
        return len;
    }

    private static int digits(int x) {
        int d = 0;
        do { d++; x /= 10; } while (x > 0);
        return d;
    }

    public static void main(String[] args) {
        System.out.println(compress("aabcccccaaa")); // a2b1c5a3
        System.out.println(compress("abcd"));        // abcd (unchanged)
        System.out.println(compress("aaaa"));        // a4
        System.out.println(compress("A  A"));        // A1 2A1
    }
}

The algorithm runs in O(n) time with a single pass over the input and uses O(1) extra space besides the output string. Some interviewers may limit counts to a single digit (e.g., split a12 into a9a3), or require the method to always return a compressed string; those variations can be handled by adjusting the digits check or removing the length‑comparison branch.