Slowest Key — Solution in Python, Java & C++
Slowest Key solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and strings.
Slowest Key is an easy coding problem on arrays and strings, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Strings
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A tester typed n keys, one after another. keysPressed[i] is the i-th key pressed and releaseTimes[i] is the moment it was released (the array is strictly increasing). The first key was pressed at time 0, and every later key was pressed at the exact moment the previous one was released.
So the i-th keypress lasted releaseTimes[i] - releaseTimes[i - 1], and the first lasted releaseTimes[0]. The same key may be pressed several times, and each press is measured on its own.
Return the key of the longest single keypress. If several presses tie for the longest, return the lexicographically largest of their keys. The answer is a one-character string.
Example 1
Input: releaseTimes = [4,9,14,16], keysPressed = "kaio"
Output: i
Explanation: Durations 4, 5, 5, 2 — `a` and `i` tie at 5 and `i` is larger.
Example 2
Input: releaseTimes = [3,10,12], keysPressed = "zrz"
Output: r
Explanation: Durations 3, 7, 2.
Example 3
Input: releaseTimes = [5,10], keysPressed = "ab"
Output: b
Constraints
releaseTimes.length == nkeysPressed.length == n2 <= n <= 10001 <= releaseTimes[i] <= 10^9releaseTimes[i] < releaseTimes[i + 1]keysPressed contains only lowercase English letters
Hints for Slowest Key
Hint 1
Compute the duration of each keypress from consecutive release times.
Hint 2
Keep the best duration seen so far and its key.
Hint 3
Replace the best when a press is strictly longer, or equally long with a larger key.
How to solve Slowest Key
Each press's duration is the gap between consecutive release times, so one pass that tracks the best (duration, key) pair under the tie rule is enough.
Approach
- Start with
bestDur = releaseTimes[0]andbestKey = keysPressed[0]. - For
ifrom 1, letd = releaseTimes[i] - releaseTimes[i-1]. - If
d > bestDur, ord == bestDurandkeysPressed[i] > bestKey, take(d, keysPressed[i])as the new best. - Return
bestKey.
Why it works
The comparison orders presses first by duration and then by key, and the pass keeps the maximum of that order — exactly the press the statement asks for. Durations are compared per press, never summed per key.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The first press lasts
releaseTimes[0], not 0. - Do not add up the durations of repeated presses of the same key.
- On a tie the larger letter wins, regardless of which press came first.
Reference solution
Python
from typing import List
def slowestKey(releaseTimes: List[int], keysPressed: str) -> str:
best_dur, best_key = releaseTimes[0], keysPressed[0]
for i in range(1, len(releaseTimes)):
d = releaseTimes[i] - releaseTimes[i - 1]
if d > best_dur or (d == best_dur and keysPressed[i] > best_key):
best_dur, best_key = d, keysPressed[i]
return best_keyJava
public static String slowestKey(int[] releaseTimes, String keysPressed) {
int bestDur = releaseTimes[0];
char bestKey = keysPressed.charAt(0);
for (int i = 1; i < releaseTimes.length; i++) {
int d = releaseTimes[i] - releaseTimes[i - 1];
char k = keysPressed.charAt(i);
if (d > bestDur || (d == bestDur && k > bestKey)) {
bestDur = d;
bestKey = k;
}
}
return String.valueOf(bestKey);
}C++
string slowestKey(vector<int>& releaseTimes, string keysPressed) {
int bestDur = releaseTimes[0];
char bestKey = keysPressed[0];
for (int i = 1; i < (int)releaseTimes.size(); i++) {
int d = releaseTimes[i] - releaseTimes[i - 1];
if (d > bestDur || (d == bestDur && keysPressed[i] > bestKey)) {
bestDur = d;
bestKey = keysPressed[i];
}
}
return string(1, bestKey);
}JavaScript
var slowestKey = function(releaseTimes, keysPressed) {
var bestDur = releaseTimes[0], bestKey = keysPressed[0];
for (var i = 1; i < releaseTimes.length; i++) {
var d = releaseTimes[i] - releaseTimes[i - 1];
if (d > bestDur || (d === bestDur && keysPressed[i] > bestKey)) {
bestDur = d;
bestKey = keysPressed[i];
}
}
return bestKey;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.