Problem Description
You are given a string keysPressed of length n, where keysPressed[i] was the i-th key pressed in the testing sequence, and a sorted list releaseTimes, where releaseTimes[i] was the time the i-th key was released. The goal is to find the key of the keypress that had the longest duration. If there are multiple such keypresses, return the lexicographically largest key.
Key Insights
- The duration of the first keypress is equal to its release time.
- The duration of subsequent keypresses can be calculated by subtracting the release time of the previous key from the current key's release time.
- If multiple keys have the same maximum duration, the lexicographically larger key should be returned.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
To solve this problem, we will iterate through the releaseTimes and keysPressed arrays, calculating the duration for each keypress. We will keep track of the maximum duration found and the corresponding key. If a new maximum duration is found, we update our key; if the same maximum duration is found, we compare the keys lexicographically and update as necessary.