Minimum Number of Pushes to Type Word I - Practice Coding Problems

Minimum Number of Pushes to Type Word I - Problem

You are given a string word containing distinct lowercase English letters.

Telephone keypads have keys mapped with distinct collections of lowercase English letters, which can be used to form words by pushing them. For example, the key 2 is mapped with ["a","b","c"], we need to push the key one time to type "a", two times to type "b", and three times to type "c".

It is allowed to remap the keys numbered 2 to 9 to distinct collections of letters. The keys can be remapped to any amount of letters, but each letter must be mapped to exactly one key.

You need to find the minimum number of times the keys will be pushed to type the string word.

Return the minimum number of pushes needed to type word after remapping the keys.

Input & Output

Example 1 — Basic Case

$ Input: word = "abcde"

› Output: 5

💡 Note: Each character appears once. Assign each to position 1 on different keys: a(1×1) + b(1×1) + c(1×1) + d(1×1) + e(1×1) = 5

Example 2 — Frequency Matters

$ Input: word = "aabbbc"

› Output: 7

💡 Note: c appears 3 times, b appears 2 times, a appears 2 times. Assign c, b, a to position 1 on keys 2, 3, 4: c(3×1) + b(2×1) + a(2×1) = 7

Example 3 — Single Character

$ Input: word = "aaa"

› Output: 3

💡 Note: Only character 'a' appears 3 times. Assign to position 1: a(3×1) = 3

Constraints

1 ≤ word.length ≤ 10⁵
word consists of distinct lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Word

Given word with distinct lowercase letters

Count & Sort

Count frequency of each character and sort by frequency

Optimal Assignment

Assign most frequent characters to easiest positions

Key Takeaway

🎯 Key Insight: Use greedy assignment to put most frequent characters in positions requiring fewest presses

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is to use a greedy approach: assign the most frequently occurring characters to keypad positions that require the fewest presses. Best approach counts character frequencies and assigns them optimally. Time: O(n + k log k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Character Counting	O(n)	O(1)	Count frequency of each character and assign to keys without optimization
Greedy Optimal Assignment	O(n + k log k)	O(k)	Assign most frequent characters to positions requiring fewest presses

Brute Force - Character Counting — Algorithm Steps

Step 1: Count frequency of each character
Step 2: Assign characters to keys 2-9 arbitrarily
Step 3: Calculate total presses based on position

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Characters

Count frequency of each character in word

Assign Positions

Assign characters to keypad positions arbitrarily

Calculate

Sum up total presses needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* word) {
    // Count frequency of each character
    int freq[26] = {0};
    int len = strlen(word);
    
    for (int i = 0; i < len; i++) {
        freq[word[i] - 'a']++;
    }
    
    // Assign characters to positions arbitrarily
    int keyPosition[26];
    int position = 1;
    
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            keyPosition[i] = position;
            position++;
            if (position > 3) {
                position = 1;
            }
        }
    }
    
    // Calculate total presses
    int totalPresses = 0;
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            totalPresses += freq[i] * keyPosition[i];
        }
    }
    
    return totalPresses;
}

int main() {
    char word[1001];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    int result = solution(word);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the word to count characters

✓ Linear Growth

Space Complexity

O(1)

Fixed space for character frequency map (at most 26 characters)

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Character Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler