algoadvance

Leetcode 1629. Slowest Key

Problem Statement

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 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. Both arrays are 0-indexed, and they are of the same length.

The duration of a key press is the time between the key’s press and release. The tester wants to know the key of the keypress that had the longest duration. If there is a tie, the key with the lexicographically largest key should be returned.

Example:

Input: releaseTimes = [9,29,49,50], keysPressed = "cbcd"
Output: "c"
Explanation: The keypress durations are as follows:
    - Key "c" has duration 9 (pressed at time 0 and released at time 9).
    - Key "b" has duration 20 (pressed at time 9 and released at time 29).
    - Key "c" has duration 20 (pressed at time 29 and released at time 49).
    - Key "d" has duration 1 (pressed at time 49 and released at time 50).
    Therefore, the key pressed with the longest duration is "b", but "c" (another key with the same duration) lexicographically comes last.

Constraints:

Clarifying Questions

  1. Are the releaseTimes guaranteed to be sorted and strictly increasing?
    • Yes, the problem statement specifies that releaseTimes[i] < releaseTimes[i+1].
  2. Can the input strings and arrays be empty?
    • No, according to the constraints, n is at least 2.
  3. Should we handle inputs outside the constraints (e.g., non-lowercase letters in keysPressed)?
    • No, we can assume the input will always meet the given constraints.

Strategy

  1. Initialize variables to track the longest duration and the corresponding key.
  2. The duration of the first key is simply releaseTimes[0].
  3. Iterate through the list from the second element, computing the duration of each key press as releaseTimes[i] - releaseTimes[i - 1].
  4. Compare each duration with the longest duration found so far:
    • If the current duration is longer, update the longest duration and corresponding key.
    • If the current duration is equal to the longest duration, update the key if it is lexicographically larger.
  5. Return the key with the longest duration.

Time Complexity

The time complexity of the solution is O(n), where n is the length of the releaseTimes and keysPressed. This is because we iterate through the input arrays only once.

Code

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    char slowestKey(vector<int>& releaseTimes, string keysPressed) {
        char slowestKey = keysPressed[0];
        int maxDuration = releaseTimes[0];
        
        for (int i = 1; i < releaseTimes.size(); ++i) {
            int duration = releaseTimes[i] - releaseTimes[i - 1];
            if (duration > maxDuration || (duration == maxDuration && keysPressed[i] > slowestKey)) {
                maxDuration = duration;
                slowestKey = keysPressed[i];
            }
        }
        
        return slowestKey;
    }
};

This code implements the strategy outlined above by:

  1. Initializing the first key and its duration as benchmarks.
  2. Iterating through subsequent keys to compare and update the longest duration and the lexicographically largest key when durations tie.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI