#1629

Easy

LeetCode Problem Workspace

Slowest Key

Determine which key had the longest press duration in a sequence using array indices and string mapping, resolving ties lexicographically.

array string

Problem Statement

You are given a testing scenario with a newly designed keypad where a sequence of n keys was pressed in order. Each keypress occurs immediately after the previous key was released, starting from time 0.

Given an array releaseTimes of length n representing the release time of each key and a string keysPressed of length n representing the keys pressed, determine the key that had the longest press duration. If multiple keys have the same maximum duration, return the lexicographically largest key.

Examples

Example 1

Input: releaseTimes = [9,29,49,50], keysPressed = "cbcd"

Output: "c"

The keypresses were as follows: Keypress for 'c' had a duration of 9 (pressed at time 0 and released at time 9). Keypress for 'b' had a duration of 29 - 9 = 20 (pressed at time 9 right after the release of the previous character and released at time 29). Keypress for 'c' had a duration of 49 - 29 = 20 (pressed at time 29 right after the release of the previous character and released at time 49). Keypress for 'd' had a duration of 50 - 49 = 1 (pressed at time 49 right after the release of the previous character and released at time 50). The longest of these was the keypress for 'b' and the second keypress for 'c', both with duration 20. 'c' is lexicographically larger than 'b', so the answer is 'c'.

Example 2

Input: releaseTimes = [12,23,36,46,62], keysPressed = "spuda"

Output: "a"

The keypresses were as follows: Keypress for 's' had a duration of 12. Keypress for 'p' had a duration of 23 - 12 = 11. Keypress for 'u' had a duration of 36 - 23 = 13. Keypress for 'd' had a duration of 46 - 36 = 10. Keypress for 'a' had a duration of 62 - 46 = 16. The longest of these was the keypress for 'a' with duration 16.

Constraints

releaseTimes.length == n
keysPressed.length == n
2 <= n <= 1000
1 <= releaseTimes[i] <= 109
releaseTimes[i] < releaseTimes[i+1]
keysPressed contains only lowercase English letters.

Solution Approach

Compute Individual Key Durations

Iterate over releaseTimes and calculate the duration for each key. The first key uses releaseTimes[0], while subsequent keys use releaseTimes[i] - releaseTimes[i - 1]. This ensures accurate mapping from the array to string positions.

Track Maximum Duration with Tie Handling

Maintain variables for max duration and current candidate key. Update these whenever a longer duration is found or when an equal duration is found and the key is lexicographically larger.

Return Result in One Pass

After a single iteration, the tracked key represents the slowest key. This approach leverages the array plus string pattern efficiently with O(N) time and O(1) space.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is O(N) since each keypress is processed once. Space complexity is O(1) because only a few variables are used regardless of array size.

What Interviewers Usually Probe

Do you recognize the pattern combining arrays and strings for tracking durations?
Watch for edge cases with multiple keys having the same maximum duration.
Consider lexicographic ordering for tie-breaking when durations match.

Common Pitfalls or Variants

Common pitfalls

Incorrectly computing durations by not subtracting consecutive release times.
Ignoring lexicographic order when multiple keys share maximum duration.
Using extra space unnecessarily instead of O(1) tracking variables.

Follow-up variants

Return the index of the slowest key instead of the character.
Handle a circular keypad where the first keypress duration starts from a nonzero time.
Consider uppercase letters or mixed characters for lexicographic tie-breaking.

FAQ

What is the main pattern used in Slowest Key?

The problem follows an array plus string pattern where array indices map directly to string characters to track durations.

How are key durations calculated?

The first key uses its release time as duration, and each subsequent key uses the difference between its release time and the previous release time.

How are ties handled when multiple keys share the same duration?

Return the lexicographically largest key among those with maximum duration.

What is the time and space complexity of the optimal solution?

Time complexity is O(N) with a single pass, and space complexity is O(1) using only tracking variables.

Can this method be used for longer sequences?

Yes, the single-pass approach scales efficiently for sequences up to the constraint limits with consistent performance.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
        ans = keysPressed[0]
        mx = releaseTimes[0]
        for i in range(1, len(keysPressed)):
            d = releaseTimes[i] - releaseTimes[i - 1]
            if d > mx or (d == mx and ord(keysPressed[i]) > ord(ans)):
                mx = d
                ans = keysPressed[i]
        return ans

Continue Practicing

#1639 number of ways to form a target string given a dictionary #1604 alert using same key card three or more times in a one hour period #1598 crawler log folder