Logic :- 1. To minimize the number of keypresses, we need to minimize the keypresses for the most frequently appearing character. For instance, if 'a' appears 5 times in a string and 'b' appears just once in that string, we must prioritize A's placement more than B's placement.
2. Create a frequency map for all characters present in your string. Then based on decreasing frequency, give top 9 characters highest priority by setting their keypress count to 1. For the next 9 (if present), allot their keypress count as 2. For remaining characters (if present), set their keypress count to 3. For e.g. if keypress count of 'G' is 2, it means it comes at 2nd spot in any of the 9 boxes and hence you will have to press that box twice to type 'G'.
import java.util.*;
class Prog1 {
static class Pair {
char ch;
int freq;
Pair(char ch, int freq){
this.ch = ch;
this.freq = freq;
}
}
public static void main(String[] args){
// Input :- String to be typed
Scanner in = new Scanner(System.in);
String str = in.nextLine();
// Complete the function minimumKeypadClickCount() below.
System.out.println(minimumKeypadClickCount(str));
}
public static int minimumKeypadClickCount(String str){
// Step 1 :- Make a frequency Map.
HashMap<Character, Integer> map = new HashMap<>();
for(int i=0;i<str.length();i++){
char ch = str.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
// Step 2 :- Now put each key-value pair as a Pair object in a maxHeap. Note that in java a heap is MinHeap by default.
PriorityQueue<Pair> pq = new PriorityQueue<>((a,b) -> b.freq - a.freq);
for(Character key : map.keySet()){
pq.add(new Pair(key, map.get(key)));
}
// Step 3 :- Remove the first 9 pairs (or less if not exactly 9) and assign them 1 as number of key-presses.
int[] keyPressCountArr = new int[26];
for(int i=1; i<=9 && pq.size() > 0; i++){
Pair pair = pq.remove();
System.out.println(pair.ch + " "+ pair.freq);
keyPressCountArr[pair.ch - 'a'] = 1;
}
// Remove the remaining 9 pairs (if available) and assign their key-presses as 2.
for(int i=1;i<=9 && pq.size()>0; i++){
Pair pair = pq.remove();
System.out.println(pair.ch + " "+ pair.freq);
keyPressCountArr[pair.ch - 'a'] = 2;
}
// Remove the remaining pairs (if available) and assign their key-presses as 3.
while(pq.size()>0){
Pair pair = pq.remove();
keyPressCountArr[pair.ch - 'a'] = 3;
}
// Step 4 :- At this point, keyPressCountArr array contains the most optimal amount of keypresses for the given string.
// Hence, calculate the answer and return it.
int ans = 0;
for(int i=0;i<str.length();i++){
char ch = str.charAt(i);
ans += keyPressCountArr[ch-'a'];
}
return ans;
}
}