3016. Minimum Number of Pushes to Type Word II

Problem Statement

Given a string word, we want to calculate the minimum number of "pushes" required to type the string. Each character in the string may need multiple pushes, depending on its frequency and position.

Approach:

In this question we have to map most frequent character with min key value so that we can achieve minimum number of pushes.

1. count frequency of each character

2. store this char, int combination into a pair class to sort this based on highest frequency

3. after sorting most frequent character assign first 1-8 character of pair list as 1, then 2-16 character as 2, and 3-24 to 3 and remaining 2 character to 4

Steps and Explanation

Step 1: Count the Frequency of Each Character

First, we need to know how many times each character appears in the string. We use a HashMap to store these frequencies.

HashMap<Character, Integer> map = new HashMap<>(); 
for (int i = 0; i < word.length(); i++) { 
  map.put(word.charAt(i), map.getOrDefault(word.charAt(i), 0) + 1); 
}

Example

For the input "aabbbcc", the map will look like this:

• a: 2

• b: 3

• c: 2

Step 2: Create a List of Pairs from the Map

We convert the map entries to a list of pairs (Pair<Character, Integer>) where each pair contains a character and its frequency. This helps us to sort the characters by their frequencies.

List<Pair<Character, Integer>> pairList = new ArrayList<>(); for (Map.Entry<Character, Integer> entry : map.entrySet()) { 
     Pair<Character, Integer> pair = new Pair<>(entry.getKey(),   entry.getValue()); pairList.add(pair); 
}

Example

The list of pairs for our example will be:

• Pair('a', 2)

• Pair('b', 3)

• Pair('c', 2)

Step 3: Sort the List of Pairs by Frequency

We sort the list of pairs in descending order based on the frequency. This ensures that characters with higher frequencies are processed first.

Collections.sort(pairList, new Comparator<Pair<Character, Integer>>() { 
@Override public int compare(Pair<Character, Integer> p1, Pair<Character, Integer> p2) { return p2.getValue().compareTo(p1.getValue()); 
} });

Example

After sorting, the list of pairs will be:

• Pair('b', 3)

• Pair('a', 2)

• Pair('c', 2)

Step 4: Assign Push Values to Characters

We assign push values to each character based on its position in the sorted list. The push value for each character is calculated as (count / 8) + 1. This ensures that characters with higher frequencies have lower push values.

int count = 0; 
for (Pair<Character, Integer> p : pairList) { 
      map.put(p.getKey(), count / 8 + 1);
      count++; 
}

Example

For our example, the push values assigned will be:

• b: 1 (since it has the highest frequency)

• a: 1 (same frequency as c, but comes next in sorted order)

• c: 1

Step 5: Calculate the Minimum Pushes

Finally, we iterate over the original string and sum up the push values of each character to get the total minimum pushes required.

int minCount = 0; 
for (int i = 0; i < word.length(); i++) { 
       minCount += map.get(word.charAt(i)); 
}

Example

For the string "aabbbcc", the push values are:

• a: 1 + 1 = 2

• b: 1 + 1 + 1 = 3

• c: 1 + 1 = 2

Total minimum pushes = 2 + 3 + 2 = 7

class Solution {
		public int minimumPushes(String word) {
			List<Pair<Character,Integer>> pairList = new ArrayList<>();

			HashMap<Character,Integer> map = new HashMap<>();
			for(int i=0;i<word.length();i++){
				map.put(word.charAt(i),map.getOrDefault(word.charAt(i),0)+1);
			}

			for(Map.Entry<Character,Integer> entry: map.entrySet()){
				Pair<Character,Integer> pair = new Pair<>(entry.getKey(),entry.getValue());
				pairList.add(pair);
			}

			Collections.sort(pairList, new Comparator<Pair<Character,Integer>> (){
				@Override
				public int compare(Pair<Character,Integer> p1, Pair<Character,Integer> p2){
					return p2.getValue().compareTo(p1.getValue());
				}
			});

			int count = 0;

			for(Pair<Character,Integer> p: pairList){
				map.put(p.getKey(), count/8+1);
				count++;
			}

			int minCount = 0;

			for(int i=0;i<word.length();i++){
				minCount += map.get(word.charAt(i));
			}

			return minCount;

		}
	}