String Compression

i/p = wwwwaaadeex

o/p = 

wadex

w4a3de2x

package jan25;

public class StringCompression {
    public static void main(String[] args) {

        String str = "wwwwaaadeex";

        System.out.println(compression1(str));
        System.out.println(compression2(str));
    }

    // compression1:
    // Time Complexity: O(n)
    // - One pass through the input string
    // Space Complexity: O(n)
    // - StringBuilder used to store result, worst case all unique characters
    private static String compression1(String str) {
        StringBuilder sb = new StringBuilder();
        sb.append(str.charAt(0));

        for (int i = 1; i < str.length(); i++) {
            char previousChar = str.charAt(i - 1);
            char currentChar = str.charAt(i);
            if (previousChar != currentChar)
                sb.append(currentChar);
        }

        return sb.toString();
    }

    // compression2:
    // Time Complexity: O(n)
    // - One pass through the input string
    // - Each character and count (if >1) appended in constant time
    // Space Complexity: O(n)
    // - StringBuilder stores compressed output, which could be up to 2n length
    private static String compression2(String str) {
        StringBuilder sb = new StringBuilder();
        sb.append(str.charAt(0));
        int count = 1;

        for (int i = 1; i < str.length(); i++) {
            char previousChar = str.charAt(i - 1);
            char currentChar = str.charAt(i);

            if (previousChar != currentChar) {
                sb.append(count != 1 ? count : "");  // Only append count if >1
                count = 1;
                sb.append(currentChar);
            } else {
                count++;
            }
        }

        sb.append(count != 1 ? count : "");  // Handle last sequence
        return sb.toString();
    }
}

📊 Time and Space Complexity Analysis:

Method
Time Complexity
Space Complexity
Explanation
compression1()
O(n)
O(n)
One pass through string; output built using StringBuilder.
compression2()
O(n)
O(n)
One pass; counts characters and conditionally appends count to builder.

n = length of input string
Both methods use a StringBuilder, which is efficient (O(1) amortized appends)