Problem 1629

Abstract / Summary

Given a release time list and a key pressed string, find which key took the longest time to be fully pressed.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1629.py

class Solution:
    def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
        prev = 0
        longest = defaultdict(int)
        for r, k in zip(releaseTimes, keysPressed):
            duration   = r - prev
            longest[k] = max(longest[k], duration)
            prev = r

        result = ""
        for c in "abcdefghijklmnopqrstuvwxyz":
            if longest[result] <= longest[c]:
                result = c
        return result
14 lines | 479 bytes | submitted November 14, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 60% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided Solution class implements a method slowestKey that determines which key was held down for the longest duration given a sequence of release timestamps and the corresponding characters pressed. The algorithm processes the input in two passes: first it computes the duration of each key press and records the maximum duration observed for each distinct character; second it iterates over the alphabet in lexical order to select the character with the greatest recorded duration, breaking ties by choosing the later character alphabetically.

Key Steps

Initialisation

The method begins by setting a variable prev to zero, which represents the timestamp of the previous key release. It also creates a defaultdict named longest that maps characters to their longest observed duration, defaulting to zero for unseen keys.

prev = 0
longest = defaultdict(int)

First Pass - Duration Calculation

The core of the first pass is a loop that zips together the list of release times and the string of pressed keys. For each pair, the duration of the current press is obtained by subtracting the previous release time from the current one. The dictionary entry for the current character is updated with the larger of the existing stored duration and the newly computed duration. Finally, prev is updated to the current release time so that the next iteration can compute the subsequent interval correctly.

for r, k in zip(releaseTimes, keysPressed):
    duration   = r - prev
    longest[k] = max(longest[k], duration)
    prev = r

Second Pass - Selecting the Result

After all durations have been recorded, the method prepares an empty string result. It then iterates over the lowercase English alphabet in order. For each character c, it compares the stored duration for c with the duration associated with the current result. If the duration for c is greater than or equal to that of result, the algorithm assigns c to result. Because the loop proceeds from 'a' to 'z', a tie (equal durations) will cause the later alphabetic character to replace the earlier one, satisfying the required tie-breaking rule.

result = ""
for c in "abcdefghijklmnopqrstuvwxyz":
    if longest[result] <= longest[c]:
        result = c
return result

Edge Cases Handled

When the input contains only a single key press, the first loop computes the duration as releaseTimes[0] - 0, correctly handling the initial offset. The defaultdict ensures that any character not yet seen has a default duration of zero, so the comparison in the second loop never raises a KeyError.

If multiple keys share the same maximum duration, the second pass’s “less than or equal” condition guarantees that the alphabetically later key overwrites the earlier one, thereby adhering to the specification for tie resolution.

When the keysPressed string includes characters that are not present in the alphabetic range (for example, uppercase letters or symbols), the second pass simply ignores them because it only iterates over 'a' through 'z'. Consequently, only lowercase letters can be returned, which matches the expected input domain.

Performance Optimizations

The algorithm uses a single pass to compute durations, avoiding any nested loops or repeated scans of the input data. By updating the maximum duration for each character on the fly, it eliminates the need for a secondary aggregation step.

The choice of a defaultdict(int) removes the overhead of explicit existence checks before updating the dictionary, allowing the max operation to be performed directly.

The second pass iterates over a fixed 26-character alphabet rather than over the potentially larger set of distinct keys present in the input. This constant-size loop guarantees that the selection step runs in predictable time regardless of input length.

Storing only the longest duration per character, rather than all individual durations, keeps the memory footprint minimal, as the dictionary never grows beyond the number of distinct lowercase letters.

Overall, the method achieves linear processing of the input list and constant-time selection of the final answer, reflecting a design that balances clarity with efficient resource usage.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a special keyboard that keeps track of how long each finger stays on a button. There is a list of times showing when each key was let go and another list showing which keys were tapped.

The computer looks at the first key press and sees how long it was held down. It remembers that time, then it looks at the next key. To know how long the second key was held, it subtracts the end time of the first key from the end time of the second key. This repeats for every button pressed.

The computer keeps a secret notepad to store the longest time each letter was held. If the letter a was held for two seconds once and then three seconds later, the computer updates the notepad to remember three.

After checking every single key, the computer looks at all the letters in the alphabet. It goes through them one by one to see which letter holds the record for the longest time. If there is a tie, it picks the letter that comes later in the alphabet.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 7 | μ = 6.62 | σ = 1.86

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fpdjsns C++
fsq C++
halfrost Go
JoshCrozier JS
lkwq007 Python
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fpdjsns C++
fsq C++
halfrost Go
JoshCrozier JavaScript
lkwq007 Python
suxrobGM C#
trung-hn Python
varunu28 Java
YuriSpiridonov Python
28 links | 18 authors | 9 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

6 solutions   November 14, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality