algoadvance

Leetcode 1629. Slowest Key

Problem Statement

You are given a string keysPressed of length n and an array releaseTimes where releaseTimes[i] denotes the time the i-th key was released. Both the string keysPressed and the array releaseTimes are of the same length.

The keypress durations are calculated as follows:

• For the first key, it is just releaseTimes[0].
• For the subsequent keys, the duration is the difference between the current and the previous release time, i.e., releaseTimes[i] - releaseTimes[i-1].

You need to return the key that had the longest duration. If there is a tie, return the lexicographically largest key.

Clarifying Questions

1. Input Constraints:
   • Could keysPressed contain lowercase English letters only?
     • Yes, keysPressed contains only lowercase English letters.
   • What is the range of the length n of keysPressed and releaseTimes?
     • 1 <= n <= 1000
2. Output Format:
   • Should the output be the specific key character?
     • Yes, the output should be the key character with the longest duration.

Strategy

1. Initialize Variables:
   • A variable max_duration to keep track of the maximum duration.
   • A variable result_key to keep track of the key with the longest duration.
2. Iterate Over the Input:
   • Calculate the duration for each key.
   • Check if the current key duration is greater than max_duration. If yes, update max_duration and result_key.
   • If the current key duration is equal to max_duration but the key is lexicographically larger than result_key, update result_key.
3. Edge Cases:
   • Single key press should be straightforward as default values will address this scenario.

Code

public class SlowestKey {
    public char slowestKey(int[] releaseTimes, String keysPressed) {
        int n = releaseTimes.length;
        char resultKey = keysPressed.charAt(0);
        int maxDuration = releaseTimes[0];

        for (int i = 1; i < n; i++) {
            int duration = releaseTimes[i] - releaseTimes[i - 1];
            if (duration > maxDuration || (duration == maxDuration && keysPressed.charAt(i) > resultKey)) {
                maxDuration = duration;
                resultKey = keysPressed.charAt(i);
            }
        }

        return resultKey;
    }

    public static void main(String[] args) {
        SlowestKey solution = new SlowestKey();
        int[] releaseTimes = {9, 29, 49, 50};
        String keysPressed = "cbcd";
        System.out.println(solution.slowestKey(releaseTimes, keysPressed)); // Output: 'c'
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of keysPressed or releaseTimes. We traverse through the list once.
• Space Complexity: O(1), as we are using only a constant extra space (variables like maxDuration, resultKey).

This solution will efficiently find the key with the longest duration while addressing ties using lexicographical order.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?