Slowest Key - Leetcode Solution

Problem:

We are given a string releaseTimes and a string keysPressed. releaseTimes[i] and keysPressed[i] represent the time at which the i-th key was released and the key which was pressed, respectively. We have to find the key with the longest duration between press and release. If there are multiple such keys, we return the lexicographically largest key.

Example:

Input: releaseTimes = [9,29,49,50], keysPressed = "cbcd" Output: "c" Explanation: The key press durations (in milliseconds) are:

• c: 29 - 9 = 20
• b: 9 - 0 = 9
• c: 49 - 29 = 20
• d: 50 - 49 = 1 c is the key with the longest duration pressed. The answer is the string "c".

Solution:

To solve this problem, we can iterate through the two given arrays, releaseTimes and keysPressed, and compute the duration of each key press. We can keep track of the maximum duration and the corresponding key. If a key has the same duration as the current maximum duration, we compare it lexicographically with the previously recorded key and update the maximum key accordingly.

Code:

class Solution { public char slowestKey(int[] releaseTimes, String keysPressed) { int maxDuration = releaseTimes[0]; // Initialize maxDuration and maxKey to the first key char maxKey = keysPressed.charAt(0); for (int i = 1; i < releaseTimes.length; i++) { int duration = releaseTimes[i] - releaseTimes[i-1]; if (duration > maxDuration || (duration == maxDuration && keysPressed.charAt(i) > maxKey)) { maxDuration = duration; maxKey = keysPressed.charAt(i); } } return maxKey; } }

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the given arrays. We iterate through the arrays only once to compute the answer.

Space Complexity:

The space complexity of this solution is O(1), as we only use a constant amount of extra space to store the maximum duration and the corresponding key.

1