Slowest Key

Easy
1184.

Slowest Key

Slowest Key is an easy coding problem on arrays and strings, asked in Amazon and Microsoft interviews.

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 == n
  • keysPressed.length == n
  • 2 <= n <= 1000
  • 1 <= releaseTimes[i] <= 10^9
  • releaseTimes[i] < releaseTimes[i + 1]
  • keysPressed contains only lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} releaseTimes
 * @param {string} keysPressed
 * @return {string}
 */
var slowestKey = function(releaseTimes, keysPressed) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 == n
  • keysPressed.length == n
  • 2 <= n <= 1000
  • 1 <= releaseTimes[i] <= 10^9
  • releaseTimes[i] < releaseTimes[i + 1]
  • keysPressed contains only lowercase English letters

Hints for Slowest Key

  1. Hint 1

    Compute the duration of each keypress from consecutive release times.

  2. Hint 2

    Keep the best duration seen so far and its key.

  3. 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

  1. Start with bestDur = releaseTimes[0] and bestKey = keysPressed[0].
  2. For i from 1, let d = releaseTimes[i] - releaseTimes[i-1].
  3. If d > bestDur, or d == bestDur and keysPressed[i] > bestKey, take (d, keysPressed[i]) as the new best.
  4. 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_key

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings