Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Better Compression

Sharing is caring!

Problem Statement
Consider a string, S, that is a series of characters, each followed by its frequency as an integer. The string is not compressed correctly, so there may be many occurrences of the same character. A properly compressed string will consist of one instance of each character in alphabetical order followed by the total count of that character within the string.

For example, the string a3c9b2c1 has two instances where ‘c’ is followed by a count: once with 9 occurrences, and again with 1. It should be compressed to a3b2c10.

Function Description
Complete the function betterCompression in the editor below. The function must return the properly compressed string.

betterCompression has the following parameter:
S: a string

Constraints
1 ≤ size of S ≤ 100000
‘a’ ≤ characters in S ≤ ‘z’
1 ≤ frequency of each character in S ≤ 1000

Sample Input For Custom Testing

a12b56c1

Sample Output

a12b56c1

Explanation
Nothing gets changed here since each character occurred only once and they are already in the sorted order.

Solution

public class BetterCompression {
    public static String betterCompression(String s) {

        char[] str = s.toCharArray();
        int[] map = new int[26];
        int i = 0;
        int n = s.length();
        while (i < n) {
            char ch = str[i];
            if (ch >= 'a' && ch <= 'z') {
                int start = i + 1;
                int end = start;
                while (end < n && (str[end] >= '0' && str[end] <= '9')) {
                    end++;
                }

                int count = Integer.parseInt(s.substring(start, end));

                map[ch - 'a'] += count;
                i = end;
            } else {
                i++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (char ch = 'a'; ch <= 'z'; ch++) {
            if (map[ch - 'a'] > 0) {
                sb.append(ch);
                sb.append(map[ch - 'a']);
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in7.txt"));
        Scanner outputScanner = new Scanner(new FileInputStream(System.getProperty("user.home") + "/" + "out7.txt"));

        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String expected = outputScanner.nextLine();
        String result = betterCompression(s);
        if (s.equals(expected)) {
            System.out.println("Fail! Expected '" + expected + "' got '" + result + "'");
        } else {
            System.out.println(result);
        }

        //System.out.println(betterCompression("a12c56a1b5"));
    }
}