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.
Example:
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.
Input: word = "xyzxyzxyzxyz" Output: 12 Explanation: The remapped keypad given in the image provides the minimum cost. "x" -> one push on key 2 "y" -> one push on key 3 "z" -> 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.
Input: word = "aabbccddeeffgghhiiiiii" Output: 24 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 "f" -> one push on key 7 "g" -> one push on key 8 "h" -> two pushes on key 9 "i" -> 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.
Constraints:
- 1 <= word.length <= 10^5
- word consists of lowercase English letters
Approach: If you see, we can only use 8 keys (2, 3, 4, ..., 9) in total that means we can type only 8 characters with one push each, then 8 characters with two pushes each and so on so the optimal way to map charaters to keys evenly.
Given the above facts we can see that it's clearly a greedy problem where we need to start with most frequent characters in sorted and try to give the minimum numnber of pushes to those characters so that we can reduce the number of pushes as much as possible.
What we can do is, we can sort the given word as per the frequency of characters in descending order. Now we can use following simple steps:
- charsAtCurrLevel = 1
- currPushes = 1
- totalPushes = 0
- i = 0
- WHILE i < n:
- totalPushes = totalPushes + Count of word[i] * currPushes
- charsAtCurrLevel = charsAtCurrLevel + 1
- IF charsAtCurrLevel > 8
- currPushes = currPushes + 1
- charsAtCurrLevel = 1
- i = i + Count of word[i]
- RETURN totalPushes
This will solve the problem in nlogn time which is good but let's see how we can improve it. As such we can't do anything but what we can do is use of constraint 2 where the string characters are only small lowercase english characters. Let's see how;
Instead of using map for collecting frequency, we can use integer array of size 26. Once we collect all the frequency, we can now sort this frequency array in descending order. Now we know every index in this frequency array is representing a character in word string so we can use following steps to calculate total pushes:
- totalPushes = 0
- currPushes = 1
- FOR i = 0 To 26
- IF freqMap[i] == 0
- BREAK
- IF i % 8 == 0
- currPushes = currPushes + 1
- totalPushes = totalPushes + freqMap[i] * currPushes
- RETURN totalPushes
That's all!
Implementation in C#:
Approach 1: Sort word based on frequency of characters:
public int MinimumPushes1(string word)
{
int length = word?.Length ?? 0;
if (length <= 8)
{
return length;
}
var wordArr = word.ToCharArray();
int[] map = new int[26];
foreach (char ch in wordArr)
{
++map[ch - 'a'];
}
Array.Sort(wordArr, (c1, c2) => {
if (map[c2 - 'a'] == map[c1 - 'a'])
{
return c1.CompareTo(c2);
}
return map[c2 - 'a'].CompareTo(map[c1 - 'a']);
});
int totalPushes = 0;
int currReqdPushes = 1;
int distintCharsAtCurrLevel = 1;
for (int i = 0; i < length; )
{
totalPushes += map[wordArr[i] - 'a'] * currReqdPushes;
++distintCharsAtCurrLevel;
if (distintCharsAtCurrLevel > 8)
{
distintCharsAtCurrLevel = 1;
++currReqdPushes;
}
i += map[wordArr[i] - 'a'];
}
return totalPushes;
}
Approach 2: Sort frequency array:
public int MinimumPushes(string word)
{
int length = word?.Length ?? 0;
if (length <= 8)
{
return length;
}
var wordArr = word.ToCharArray();
int[] map = new int[26];
foreach (char ch in word)
{
++map[ch - 'a'];
}
Array.Sort(map, (i1, i2) => {
return i2.CompareTo(i1);
});
int totalPushes = 0;
int currReqdPushes = 1;
for (int i = 0; i < 26; ++i)
{
if (map[i] == 0)
{
break;
}
if (i != 0 && i % 8 == 0)
{
++currReqdPushes;
}
totalPushes += map[i] * currReqdPushes;
}
return totalPushes;
}
Complexity: Approach 1: O(nlogn)
Approach 2: O(n)
No comments:
Post a Comment