Slowest Key — LeetCode 1629 Python Solution

The problem

A newly designed keypad was tested, where a tester pressed a sequence of n keys, one at a time. You are given a string keysPressed of length n, where keysPressed[i] was the ith key pressed in the testing sequence, and a sorted list releaseTimes, where releaseTimes[i] was the time the ith key was released.

Example

Input

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

Output

"c"

Explanation

The keypresses were as follows:

Python solution

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

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1629. Slowest Key is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems