101A – Homework

A greedy problem.
You’re given a string and allowed to remove up to m characters from it. Your goal is to choose the removed characters such that the number of distinct characters in the remaining string is minimized.
Simply, on taking input, calculate the frequency of each character and sort the frequencies. Characters with less frequency are candidate to removal more than any other ones. That’s the key point and the rest is straight-forward.
Java implementation:

import java.util.*;

public class Main {
	int m;
	static LetterAndFreq[] lst = new LetterAndFreq[26];
	static HashSet<Character> map = new HashSet<Character>();

	public static void main(String[] args) {
		// init
		for (int i = 0; i < lst.length; i++)
			lst[i] = new LetterAndFreq((char) ('a' + i), 0);
		Scanner s = new Scanner(System.in);
		// input
		String line = s.nextLine();
		int m = s.nextInt();
		for (int i = 0; i < line.length(); i++) {
			lst[line.charAt(i) - 'a'].f++;
			map.add(line.charAt(i));
		}
		// solve
		Arrays.sort(lst);
		for (int i = 0; map.size() > 0 && lst[i].f <= m; i++)
			if (lst[i].f != 0) {
				m -= lst[i].f;
				map.remove(lst[i].l);
			}
		// print
		System.out.println(map.size());
		for (int i = 0; i < line.length(); i++)
			if (map.contains(line.charAt(i)))
				System.out.print(line.charAt(i));
		System.out.println();
	}

	static class LetterAndFreq implements Comparable<LetterAndFreq> {
		char l; int f;
		public LetterAndFreq(char i, int j) { l = i; f = j; }
		public int compareTo(LetterAndFreq o) { return f - o.f; }
	}

}