CodingGyan

Run-Length Encoding

easy Strings

Problem

Read one word. Replace every run of the same character by the character followed by the length of the run. Example: aaabbc becomes a3b2c1.

Constraints

  • 1 <= length <= 10^5, letters only

Examples

Input

aaabbc

Output

a3b2c1

Solutions

Best approachTime O(n)Space O(n)

A run is a block of equal characters. For each run we write the character and its length. i marks the start of the run and j finds its end.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process one line of text.
 * Input   : One line of text.
 * Output  : Compress runs.
 * Approach: Find each run, write its length.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String solve(String s) {
        // Step 1: The answer is built in a StringBuilder.
        StringBuilder result = new StringBuilder();
        int i = 0;

        // Step 2: Handle one run at a time.
        while (i < s.length()) {
            char current = s.charAt(i);

            // Step 3: Move j forward while the characters are the same.
            int j = i;
            while (j < s.length() && s.charAt(j) == current) {
                j++;
            }

            // Step 4: Write the character and the length of its run.
            result.append(current).append(j - i);

            // Step 5: Continue after this run.
            i = j;
        }
        return result.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(solve(s));
    }
}
Hints (1)
  1. Where does a run end?

Try these next