3016. Minimum Number of Pushes to Type Word II

MediumView on LeetCode

String Greedy Sorting Hash Table Counting

Time: O(n + 26 log 26)

Space: O(26)

Problem Overview

Same keypad idea as LC 3014: 8 letter keys, stacked push costs.

Intuition

Same keypad idea as LC 3014: 8 letter keys, stacked push costs. Word II allows repeated letters, so frequency matters. Sort letter frequencies descending and assign the busiest letters to the cheapest push tiers (cost i/8 + 1 for the i-th busiest letter).

Algorithm

1Count frequency of each letter a..z.
2Sort the 26 counts ascending.
3For rank i = 0..25 from the largest count, add count[25-i] * (i/8 + 1).
4Return the total pushes.

Example Walkthrough

Input: word = "xyzxyzxyzxyz"

1.x, y, z each appear 4 times.
2.Three busiest letters all fit in the first press tier (cost 1).
3.Total = 4+4+4 = 12.

Output: 12

Common Pitfalls

•Do not treat this like Part I with distinct letters only - duplicates change which letters earn cheap slots.
•Cost jumps every 8 letters: ranks 0..7 cost 1, 8..15 cost 2, and so on.
•Sort frequencies, not the raw string characters.
•Zero counts after sorting contribute nothing at the low end.

3016.cs

// Approach: Frequency sort; assign highest-freq chars to fewest-press keys (8 chars per press tier).
// Time: O(n + 26 log 26) Space: O(26)

public class Solution
{
    public int MinimumPushes(string word)
    {
        int ans = 0;
        int[] count = new int[26];

        foreach (char ch in word)
            ++count[ch - 'a'];

        Array.Sort(count);

        for (int i = 0; i < 26; i++)
            ans += count[26 - i - 1] * (i / 8 + 1);

        return ans;
    }
}

Was this solution helpful?