Challenge: Shrink the Text

Lab Java Intermediate 20 points

Compress a word by replacing each run of the same letter with the letter and the run length: aaabccdddd becomes a3b1c2d4. If the compressed text is not shorter than the original, print the original instead.

Input

One word of letters.

Output

The compressed word, or the original if compressing doesn't help.

Example

Input

aaabccdddd

Output

a3b1c2d4

Sample input available Sample output available

Editor

Java

Hints

Find where each run of the same letter ends with an inner loop.

Use a StringBuilder for the answer, then compare lengths.

Solution explanation

The inner loop moves j forward and i jumps to j, so every character is visited once: O(n), not O(n²).

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            int j = i;
            while (j < s.length() && s.charAt(j) == c) j++;   // find the end of this run
            sb.append(c).append(j - i);
            i = j;
        }
        System.out.println(sb.length() < s.length() ? sb.toString() : s);
    }
}

Output

Answer