Nine-Button Layout

Medium

You are designing a phone with nine buttons and get to decide which lowercase English letters go on which button. The rules are: - each of the 26 letters is on exactly one button; - a button holds at most three letters. To type the letter that sits k-th on its button, you press that button k times in a row. You are given a string text. The layout is chosen once, and then the whole text is typed on it. Return the smallest possible total number of presses.

Example 1

text="tomato" → 6

There are only four distinct letters, so each can sit first on its own button. Six letters, six presses.

Example 2

text="abcdefghijj" → 12

There are ten distinct letters. j appears twice, so it goes first on a button (2 presses). Eight more letters are also first (8 presses), and the last one has to sit second on some button (2 presses). Total: 12.

Constraints

1 ≤ len(text) ≤ 10⁵
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Hash Table String Counting Sorting

Similar problems

No Twin Letters Side by Side Medium Reassigning the Phone Keypad Medium Palindromes From Shared Letters Medium Fill the Blanks With the Fewest Repeats Medium Even Out Letter Counts Medium

Input

text="tomato"

Expected

Run checks the first 3 tests in your browser. Submit checks all 78 tests on the server, hidden ones included.