EasyNo. 0925
Long Pressed Name — LeetCode 925 Python Solution
- Pattern
- Two Pointers
- Topics
- Two Pointers, String
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.
Example
- Input
- name = "alex", typed = "aaleex"
- Output
- true
- Explanation
- 'a' and 'e' in 'alex' were long pressed.
Python solution
class Solution:
def isLongPressedName(self, name: str, typed: str) -> bool:
m, n = len(name), len(typed)
i = j = 0
while i < m and j < n:
if name[i] != typed[j]:
return False
x = i + 1
while x < m and name[x] == name[i]:
x += 1
y = j + 1
while y < n and typed[y] == typed[j]:
y += 1
if x - i > y - j:
return False
i, j = x, y
return i == m and j == nComplexity
- Time
- O(m + n), where m and n are the lengths of the strings `name` and `typed` respectively
- Space · auxiliary
- $O(1)`
Pattern: Two Pointers
Use the order already in the input to discard half the search space at every step. LeetCode 925. Long Pressed Name is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.
The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0917 | Reverse Only Letters | Easy |
| 0005 | Longest Palindromic Substring | Medium |
| 0028 | Find the Index of the First Occurrence in a String | Easy |
| 0125 | Valid Palindrome | Easy |
| 0151 | Reverse Words in a String | Medium |
| 0165 | Compare Version Numbers | Medium |
Frequently asked questions
- How hard is LeetCode 925. Long Pressed Name?
LeetCode 925. Long Pressed Name is rated Easy on LeetCode.
- What is the time complexity of LeetCode 925. Long Pressed Name?
The Python solution on this page runs in O(m + n), where m and n are the lengths of the strings `name` and `typed` respectively.
- What is the space complexity of LeetCode 925. Long Pressed Name?
The Python solution on this page uses $O(1)` auxiliary space.
- What topics does LeetCode 925. Long Pressed Name cover?
LeetCode 925. Long Pressed Name is tagged Two Pointers and String on LeetCode.