Minimum Number of Pushes to Type Word II

You may assign the 26 lowercase English letters to eight keys, numbered 2 through 9. Each key holds an ordered list of letters, and every letter must appear on exactly one key. A key may hold any number of letters, including none.

Typing the first letter on a key takes one push, its second letter takes two pushes, and so on. Choose a single mapping to minimize the total pushes needed to type word, and return that minimum. The cost of typing each occurrence is counted independently.

Example 1:

Input: word = "abcdefghijk"

Output: 14

Explanation: Assign eight letters to the first positions on the eight keys, costing 8 pushes. The remaining three letters use second positions, costing 6 more. The minimum is 14.

Example 2:

Input: word = "zzzzabcd"

Output: 8

Explanation: There are only five distinct letters. Put each first on a different key, so all eight characters take one push apiece.

Example 3:

Input: word = "abcdefghijklmnopqrstuvwxyz"

Output: 56

Explanation: The first eight letters can cost one push each, the next eight cost two, the next eight cost three, and the final two cost four. The total is 8 + 16 + 24 + 8 = 56.

Constraints:

• 1 <= word.length <= 100000
• word contains only lowercase English letters.