Alg.12 Run-Length Encoding

From algoexpert.io

Here is the introduction of Run_Length Encoding: https://en.wikipedia.org/wiki/Run-length_encoding

Code implementation

public String runLengthEncoding(String string) {
        StringBuilder result = new StringBuilder();
        int currentLength = 1;
        
        for (int i = 1; i < string.length(); i++) {
            char cur = string.charAt(i);
            char prev = string.charAt(i - 1);
            if (cur != prev || currentLength == 9) {
                result.append(Integer.toString(currentLength));
                result.append(prev);
                currentLength = 0;
            }
            currentLength++;
        }
        
        result.append(Integer.toString(currentLength));
        result.append(string.charAt(string.length() - 1));
    return result.toString();
  }

Pay attention to the edge condition, after we finish the iteration, there are two conditions: 1. the last character is different from its preceding character, or 2. the last character is the same as the previous one. We need to append another integer and character under both conditions.

Time complexity: O(n); Space complexity: O(n)

Donate