0 like 0 dislike
2,196 views
| 2,196 views

0 like 0 dislike

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.

}

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()){

}

// 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;

}

}```
by (440 points)
selected
0 like 0 dislike
#include<bits/stdc++.h>

using namespace std;

int main()

{

string s;
cin>>s;

//taking the frequeency of all characters so that we can know which are most pressed characters so that  if

map these most clicked to minimum numbers we can reduce the overall click rate

map<char,int>map;

for(int i=0;i<s.size();i++)
map[s[i]]++;

//sorting  the string
sort(s.begin(),s.end());

//taking three counts that maintain 1click 2click and 3click positions

int cnt1=9;
int cnt2=9;
int cnt3=9;

int ans=0;
int i=0;
while(i<s.size())
{
if(cnt1!=0)
{
ans+=map[s[i]]*1;
cnt1--;
}
else if(cnt2!=0)
{
ans+=map[s[i]]*2;
cnt2--;
}
else
{
ans+=map[s[i]]*3;
cnt3--;
}

i+=map[s[i]];

}

cout<<ans;

}
by (140 points)
0 like 0 dislike

IMAGE OF THE QUES

by Expert (46,090 points)