Minimum Number of Keypresses
- 1 min read
- String
- LC-Medium
3 years ago
Solution
- Use a greedy approach where you map each character to an index one at a time, do this cyclically while incrementing index
- The only thing here is to sort the string in descending order of frequency, so that you minimize the keypresses, i.e. the most frequency keys should ideally be pressed only once or twice, at worst case 3 times
- To achieve this, instead of normally iterating through each character in the string, iterate through characters sorted in descending order of their frequency in the string
| Time | Space | Explanation | |
|---|---|---|---|
O() | O() |
def minimumKeypresses(self, s: str) -> int:
keys = [0] * 9
i = 0
key_presses = 0
most_frequent = {k: v for k, v in sorted(Counter(s).items(), reverse=True, key=lambda x:x[1])}
mapped = defaultdict(lambda: 0)
for ch, freq in most_frequent.items():
if ch not in mapped:
keys[i] = min(keys[i] + 1, 3)
mapped[ch] = keys[i]
i = (i + 1) % 9
key_presses += (mapped[ch] * freq)
return key_presses