1629-slowest-key.cpp

// Title: Slowest Key
// Description:
//     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.
//     Both arrays are 0-indexed. The 0th key was pressed at the time 0, and every subsequent key was pressed at the exact time the previous key was released.
//     The tester wants to know the key of the keypress that had the longest duration.
//     The ith keypress had a duration of releaseTimes[i] - releaseTimes[i - 1], and the 0th keypress had a duration of releaseTimes[0].
//     Note that the same key could have been pressed multiple times during the test, and these multiple presses of the same key may not have had the same duration.
//     Return the key of the keypress that had the longest duration. If there are multiple such keypresses, return the lexicographically largest key of the keypresses.
// Link: https://leetcode.com/problems/slowest-key/

// Time complexity: O(n)
// Space complexity: O(1)
class Solution {
public:
    char slowestKey(vector<int>& releaseTimes, string keysPressed) {
        int maxDuration = 0;
        char maxKey = '\0';
        
        // find the key with the longest duration
        int lastReleaseTime = 0;
        for (std::size_t i = 0; i < releaseTimes.size(); i++) {
            int duration = releaseTimes[i] - lastReleaseTime;
            char key = keysPressed[i];
            
            if (duration > maxDuration || duration == maxDuration && key > maxKey) {
                maxDuration = duration;
                maxKey = key;
            }
                
            lastReleaseTime = releaseTimes[i];
        }
        
        return maxKey;
    }
};