DDSA Solutions

3014. Minimum Number of Pushes to Type Word I

EasyView on LeetCode
ArrayStringGreedySortingCounting

Problem Overview

A phone keypad has 8 letter keys.

Intuition

A phone keypad has 8 letter keys. Each key can hold several letters stacked by push count (1st letter = 1 push, 2nd = 2 pushes, ...). To minimize total pushes, put the most frequent letters in the cheapest slots. With at most 26 letters, the eight cheapest slots are the first press on each key, then the second press, and so on.

Algorithm

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

Example Walkthrough

Input: word = "abcde"

  1. 1.Five distinct letters, each frequency 1.
  2. 2.Ranks 0..4 all use cost i/8+1 = 1.
  3. 3.Total pushes = 5.

Output: 5

Common Pitfalls

  • •Only 8 keys matter for letters - cost increases every 8 letters (i/8 + 1).
  • •Sort frequencies, not the characters of word, so rare letters take expensive slots.
  • •Zero-frequency letters after sorting sit at the front and contribute nothing.
  • •Part I usually has distinct letters; counting still handles repeats correctly.
3014.cs
C#
public class Solution
{
    // Approach: Remap letters onto 8 phone keys. More frequent letters should
    // need fewer key presses. Count frequencies, sort ascending, then assign
    // from most frequent: the i-th busiest letter costs (i/8 + 1) presses.
    // Complexity: O(1) time after the O(n) count (26 letters), O(1) space.
    public int MinimumPushes(string word)
    {
        int ans = 0;
        int[] count = new int[26];

        foreach (char c in word)
            ++count[c - '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?

Related Problems