Minimum Number of Pushes to Type Word I
Source: leetcode
Difficulty: Easy
Tags: math, string, greedy

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*.


An example mapping of letters to keys on a telephone keypad is given below. Note that `1`, `*`, `#`, and `0` do **not** map to any letters.


![](https://assets.leetcode.com/uploads/2023/12/26/keypaddesc.png)
 


**Example 1:**


![](https://assets.leetcode.com/uploads/2023/12/26/keypadv1e1.png)

```

Input: word = "abcde"
Output: 5
Explanation: The remapped keypad given in the image provides the minimum cost.
"a" -> one push on key 2
"b" -> one push on key 3
"c" -> one push on key 4
"d" -> one push on key 5
"e" -> one push on key 6
Total cost is 1 + 1 + 1 + 1 + 1 = 5.
It can be shown that no other mapping can provide a lower cost.

```

**Example 2:**


![](https://assets.leetcode.com/uploads/2023/12/26/keypadv1e2.png)

```

Input: word = "xycdefghij"
Output: 12
Explanation: The remapped keypad given in the image provides the minimum cost.
"x" -> one push on key 2
"y" -> two pushes on key 2
"c" -> one push on key 3
"d" -> two pushes on key 3
"e" -> one push on key 4
"f" -> one push on key 5
"g" -> one push on key 6
"h" -> one push on key 7
"i" -> one push on key 8
"j" -> one push on key 9
Total cost is 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12.
It can be shown that no other mapping can provide a lower cost.

```

 


**Constraints:**


- `1 <= word.length <= 26`
- `word` consists of lowercase English letters.
- All letters in `word` are distinct.




C++ solution:
class Solution {
public:
    int minimumPushes(string word) {
        int n = word.size();
        if(n <= 8)return n;
        if(n <= 16) return (n-8) * 2 + 8;
        if(n <= 24) return (n-8) * 3 ;

        if(n == 25)return 52;
        return 56;
    }
};
/*
xycdefghij
cdefghijxy
9 -> 10
10 -> 12
11 -> 14
12 -> 16
13 -> 18
14 -> 20
15 -> 22
16 -> 24
17 -> 27
18
19
20
21
22
23
24
25 -> + 52

26 -> + 56

  cx  dy
ea  fb  g
h  i  jklmnopqrstuvwz  
*/

Go solution:
func minimumPushes(word string) int {
	length := len(word)

	pushes := 0
	if length <= 8 {
		pushes += (1 * length)
	} else if length <= 16 {
		pushes += (1 * 8) + (2 * (length - 8))
	} else if length <= 24 {
		pushes += (1 * 8) + (2 * 8) + (3 * (length - 16))
	} else {
		pushes += (1 * 8) + (2 * 8) + (3 * 8) + (4 * (length - 24))
	}

    return pushes
}

// MORE GENERIC SOLUTION -> IF LENGTH OF WORD IS LARGE
// func minimumPushes(word string) int {
// 	freqChars := make([]int, 26)
// 	for i := 0; i < len(word); i++ {
// 		freqChars[word[i]-'a']++
// 	}
// 	sort.Slice(freqChars, func(i, j int) bool {
// 		return freqChars[i] > freqChars[j]
// 	})
// 	pushes := 0
// 	for i := 0; i < 26; i++ {
// 		if i < 8 {
// 			pushes += freqChars[i]
// 		} else if i < 16 {
// 			pushes += (freqChars[i] * 2)
// 		} else if i < 24 {
// 			pushes += (freqChars[i] * 3)
// 		} else {
// 			pushes += (freqChars[i] * 4)
// 		}
// 	}
// 	return pushes
// }

Java solution:
class Solution {
    public int minimumPushes(String word) {
        int d = word.length() / 8;
        int m = word.length() % 8;

        return 4 * d * (d + 1) + m * (d + 1);
    }
}

JavaScript solution:
/**
 * @param {string} word
 * @return {number}
 */
var minimumPushes = function(word) {
    let n= word.length,keyPress=0,f=1
    while(n!==0){
        
        if(n<=8){
            return keyPress+(n*f)
        }

        n-=8
        keyPress+=8*f
        f++
        
    }
};

Python solution:
class Solution:
    def minimumPushes(self, word: str) -> int:
        size = len(word)
        push = 1
        total = 0
        while size > 0:
            if size > 8:
                total += 8 * push
                size -= 8
            else:
                total += size * push
                size = 0
            push += 1

        return total

Ruby solution:
def minimum_pushes(word)
  number_of_keys = 8

  quotient, modulus = word.length.divmod(number_of_keys)

  divisible_pushes = (1..quotient).sum { _1 * number_of_keys }
  remainder_of_pushes = modulus * (quotient + 1)

  divisible_pushes + remainder_of_pushes
end