<p>You are given a string <code>word</code> containing lowercase English letters.</p>

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

<p>It is allowed to remap the keys numbered <code>2</code> to <code>9</code> to <strong>distinct</strong> collections of letters. The keys can be remapped to <strong>any</strong> amount of letters, but each letter <strong>must</strong> be mapped to <strong>exactly</strong> one key. You need to find the <strong>minimum</strong> number of times the keys will be pushed to type the string <code>word</code>.</p>

<p>Return <em>the <strong>minimum</strong> number of pushes needed to type </em><code>word</code> <em>after remapping the keys</em>.</p>

<p>An example mapping of letters to keys on a telephone keypad is given below. Note that <code>1</code>, <code>*</code>, <code>#</code>, and <code>0</code> do <strong>not</strong> map to any letters.</p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/12/26/keypaddesc.png" style="width: 329px; height: 313px;" />
<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/12/26/keypadv1e1.png" style="width: 329px; height: 313px;" />
<pre>
<strong>Input:</strong> word = &quot;abcde&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> The remapped keypad given in the image provides the minimum cost.
&quot;a&quot; -&gt; one push on key 2
&quot;b&quot; -&gt; one push on key 3
&quot;c&quot; -&gt; one push on key 4
&quot;d&quot; -&gt; one push on key 5
&quot;e&quot; -&gt; 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/12/26/keypadv2e2.png" style="width: 329px; height: 313px;" />
<pre>
<strong>Input:</strong> word = &quot;xyzxyzxyzxyz&quot;
<strong>Output:</strong> 12
<strong>Explanation:</strong> The remapped keypad given in the image provides the minimum cost.
&quot;x&quot; -&gt; one push on key 2
&quot;y&quot; -&gt; one push on key 3
&quot;z&quot; -&gt; one push on key 4
Total cost is 1 * 4 + 1 * 4 + 1 * 4 = 12
It can be shown that no other mapping can provide a lower cost.
Note that the key 9 is not mapped to any letter: it is not necessary to map letters to every key, but to map all the letters.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/12/27/keypadv2.png" style="width: 329px; height: 313px;" />
<pre>
<strong>Input:</strong> word = &quot;aabbccddeeffgghhiiiiii&quot;
<strong>Output:</strong> 24
<strong>Explanation:</strong> The remapped keypad given in the image provides the minimum cost.
&quot;a&quot; -&gt; one push on key 2
&quot;b&quot; -&gt; one push on key 3
&quot;c&quot; -&gt; one push on key 4
&quot;d&quot; -&gt; one push on key 5
&quot;e&quot; -&gt; one push on key 6
&quot;f&quot; -&gt; one push on key 7
&quot;g&quot; -&gt; one push on key 8
&quot;h&quot; -&gt; two pushes on key 9
&quot;i&quot; -&gt; one push on key 9
Total cost is 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24.
It can be shown that no other mapping can provide a lower cost.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= word.length &lt;= 10<sup>5</sup></code></li>
	<li><code>word</code> consists of lowercase English letters.</li>
</ul>

class Solution {
public:
// naive solution
// idea - the most frequent letters should cost less pushes
// 
// count frequencies of each letter in word
// sort letters by their frequencies in descending order
// 'place' the most frequent letters as close to the beginnning in button as possible

// xyzaabbccddeeffffggggghhhhhiiiiiiii
// x-1 y-1 z-1 a-2 b-2 c-2 e-2 f-4 g-5 h-5 i-8

// i-8 g-5 h-5 f-4 a-2 b-2 c-2 e-2 x-1 y-1 z-1


//  1       2 ix    3 gy

//  4 hz    5 f     6 a

//  7 b     8 c     9 e  

//  *       0       #

// i-1 g-1 h-1 f-1 a-1 b-1 c-1 e-1 x-2 y-2 z-2    

// time complexety O(n) 
// memory required O(1)
    int minimumPushes(const std::string& word) {
        static constexpr int alphabetSize = 26;

        // count frequencies
        std::unordered_map<char, int> frequencies;
        frequencies.reserve(alphabetSize);

        for (char letter : word) {
            if (frequencies.find(letter) == frequencies.end()) {
                frequencies.insert({letter, 0});
            }

            ++(frequencies.at(letter));
        }

        // sort by frequency
        // TODO: use std::array because size is always 26
        std::vector<std::pair<char, int>> frequenciesSorted(frequencies.begin(), frequencies.end());
        sort(frequenciesSorted.begin(),
             frequenciesSorted.end(),
             [](const std::pair<char, int>& left, const std::pair<char, int>& right) -> bool {
                return left.second > right.second;
             });

        // 0   1   2   3   4   5   6   7   8   9   10
        // i-1 g-1 h-1 f-1 a-1 b-1 c-1 e-1 x-2 y-2 z-2    

        // counter number of pushes
        int counter = 0;
        const int size1 = 8 < frequenciesSorted.size() ? 8 : frequenciesSorted.size();
        for (int i = 0; i < size1; ++i) {
            counter += (1 * frequencies.at(frequenciesSorted[i].first));
        }
        const int size2 = 16 < frequenciesSorted.size() ? 16 : frequenciesSorted.size();
        for (int i = size1; i < size2; ++i) {
            counter += (2 * frequencies.at(frequenciesSorted[i].first));
        }
        const int size3 = 24 < frequenciesSorted.size() ? 24 : frequenciesSorted.size();
        for (int i = size2; i < size3; ++i) {
            counter += (3 * frequencies.at(frequenciesSorted[i].first));
        }
        const int size4 = frequenciesSorted.size();
        for (int i = size3; i < size4; ++i) {
            counter += (4 * frequencies.at(frequenciesSorted[i].first));
        }
        

        return counter;
    }
};
16590