algoadvance

Leetcode 3014. Minimum Number of Pushes to Type Word I

Problem Statement

The problem statement for the LeetCode problem “Minimum Number of Pushes to Type Word I-out” reads as follows:

You are given a keyboard similar to an old mobile phone, where each key corresponds to some characters. You need to find the minimum number of pushes required to type out a given word.

• Each key can be pressed multiple times to cycle through its characters.
• You can press a key to start cycling through its characters, and if you press it more than one time consecutively, it will continue to the next character.
• You can use different keys for different characters in the word.

The keyboard is described by an array, where each element is a string representing the characters that can be typed using the corresponding key.

You need to implement a function that determines the minimum pushes required.

Clarifying Questions

1. Input Consistency: Can we assume the length of the keyboard array and the maximum length of each string within the array are consistent?
2. Character Coverage: Do all keys collectively cover all lowercase English letters?
3. Case Sensitivity: Are the inputs and required characters case-sensitive, i.e., do we consider only lowercase characters?
4. Edge Cases: Should we consider empty strings or inputs provided?

Let’s make some assumptions based on typical constraints:

• We assume the keyboard array covers all characters in the target word.
• The inputs will be only lowercase characters.

Sample Input/Output

Let’s illustrate with an example to make sure we understand the scenario clearly:

Example:

• Keyboard: ["abc", "def", "ghi"]
• Word: "ace"
• Output: 6 (Explanation: To type “ace”, the keys would be pressed as follows: press key 1 -> ‘a’ (1 time), key 3 -> ‘c’ (3 times), key 2 -> ‘e’ (2 times). Total = 1 + 3 + 2 = 6.)

Strategy

To solve this problem, we can follow these steps:

1. Create a map to associate each character with the required keypresses:
   • Iterate over the keyboard array.
   • For each key (string in the array), map each character to the count of its position (1-based) within the string.
2. Use this map to compute the minimum total keypresses for the given word:
   • For each character in the word, sum up the corresponding keypress count from the map.

Code

Here is a possible implementation of the solution in C++:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

int minPushesToTypeWord(vector<string>& keyboard, string word) {
    unordered_map<char, int> keyPressMap;

    // Create the map for each character's key press count from the keyboard
    for (int i = 0; i < keyboard.size(); ++i) {
        string keyGroup = keyboard[i];
        for (int j = 0; j < keyGroup.size(); ++j) {
            keyPressMap[keyGroup[j]] = j + 1;
        }
    }

    // Calculate the total number of key presses required for the word
    int totalPushes = 0;
    for (char c : word) {
        if (keyPressMap.find(c) != keyPressMap.end()) {
            totalPushes += keyPressMap[c];
        }
    }

    return totalPushes;
}

int main() {
    vector<string> keyboard = {"abc", "def", "ghi"};
    string word = "ace";
    
    int result = minPushesToTypeWord(keyboard, word);
    cout << "Minimum number of pushes: " << result << endl;

    return 0;
}

Time Complexity

• Building the Map: O(n * m), where n is the number of strings in the keyboard and m is the average length of the strings.
• Calculating Total Pushes: O(k), where k is the length of the target word.

The overall complexity is O(n * m + k), which should be efficient for reasonable input sizes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?