String Compression

Implement a method to perform basic string compression using the counts of repeated characters.

For example, the string

String input = "aabcccccaaa";
String output = "a2b1c5a3";

If the “compressed” string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

👉 Link here to the repo to solve the problem

👌 Tips

Do the easy thing first. Compress the string, then compare the lengths.

Be careful you are not repeatedly concatenating strings together. This can be very inefficient.

👊 Solution 1

A simple solution concatenating could work, however it would not be efficient. Its runtime would be O (S + K ^ 2), where S is the length of the String and K is the number of character sequences. For example, if the String is "aabccdeeaa" there would be 6 character sequences. Remember also that concatenating strings without a StringBuilder takes O(N ^ 2).

String ineficientSolution(String str) {
    String compressed = "";
    int count = 0;
    for (int i = 0; i < str.length(); i++) {
      count++;
      if (i + 1 >= str.length() && str.charAt(i) != str.charAt(i + 1)) {
        compressed+= "" + str.charAt(i) + count;
        count = 0;
      }
    }

    return compressed.length() < str.length() ? compressed : str;
  }

👊 Solution 2

Let’s optimise the first solution this time using a StringBuilder:

String stringBuilderSolution(String str) {
    int length = str.length();
    char current = str.charAt(0);
    int count = 0;
    StringBuilder compressed = new StringBuilder();

    for (int i = 0; i < length; i++) {
      char c = str.charAt(i);
      if (c == current) {
        count++;
      } else {
        compressed.append(current).append(count);
        current = c;
        count = 1;
      }
    }
    compressed.append(current).append(count);

    return compressed.length() < length ? compressed.toString() : str;
  }

---

Borrowed question from the book “Cracking the coding interview”