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.

Long Pressed Name — LeetCode 925 Python Solution

EasyTwo PointersString

Problem: #925
Pattern: Two Pointers
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

Python

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 == n

Complexity

Measure	Complexity
Time	O(m + n), where m and n are the lengths of the strings `name` and `typed` respectively
Space	$O(1)` auxiliary

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.

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.