Jobs

Interviews

Discussions

Long Pressed Name

#758 Most AskedEasy

Long Pressed Name #758 Most Asked

Easy

Google

11 views

Topics:

StringsTwo Pointers

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.

You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it was not in the typed output.

Constraints:

1 <= name.length, typed.length <= 1000
name and typed consist of only lowercase English letters.

Try coding it in LeetCode

Long Pressed Name

#758 Most AskedEasy

Long Pressed Name #758 Most Asked

Easy

Google

11 views

Topics:

StringsTwo Pointers

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.

You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it was not in the typed output.

Constraints:

1 <= name.length, typed.length <= 1000
name and typed consist of only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can both `name` and `typed` be empty strings, and if so, what should the return value be?
Can `name` or `typed` contain characters other than lowercase letters (e.g., uppercase, numbers, special characters)?
Is it guaranteed that `name` is a valid name and won't have adjacent different characters that are the same (e.g., "aab"), and `typed` similarly is the 'typed' result of a long press of `name`?
If `typed` contains extra characters not present in `name` at all, should I return false?
What is the maximum length of the `name` and `typed` strings?

Brute Force Solution

Approach

The brute force approach to this problem involves meticulously checking if each character in the 'typed' name can possibly come from the original 'name'. We will look at 'typed' character by character and try to account for each one using the original 'name'.

Here's how the algorithm would work step-by-step:

Start by comparing the first character of the 'name' with the first character of the 'typed' name.
If they match, move to the next character in both names.
If the characters don't match, check if the current character in 'typed' is the same as the previous character in 'typed'. If it is, we assume it's a long press and move to the next character in 'typed'.
If the characters don't match and the current character in 'typed' is different than the previous character in 'typed', then the 'typed' name can't be a long press of 'name'. Return that it's not possible.
Keep repeating these comparisons until you reach the end of the 'typed' name.
After reaching the end of the 'typed' name, make sure we have also reached the end of the original 'name'. If we haven't, that also means the typed name could not have been generated from the original name.
If we reach the end of both names using these steps, then the 'typed' name is a valid long press of the original 'name'.

Code Implementation

def is_long_pressed_name(name, typed): 
    name_index = 0
    typed_index = 0

    while typed_index < len(typed):
        if name_index < len(name) and name[name_index] == typed[typed_index]:
            name_index += 1
            typed_index += 1

        # Check for long press
        elif typed_index > 0 and typed[typed_index] == typed[typed_index - 1]:
            typed_index += 1

        # If chars don't match and it's not a long press, return False
        else:
            return False

    # Check if we've reached the end of the original name
    if name_index != len(name):
        return False

    return True

Big(O) Analysis

Time Complexity

O(n + m) – The algorithm iterates through the 'name' string (length n) and the 'typed' string (length m) using two pointers. In the best-case scenario, where 'typed' perfectly matches 'name', both pointers increment together. In the worst-case scenario, where there are long presses in 'typed', the 'typed' pointer will increment more frequently, but still in a linear manner related to the length of the 'typed' string. Therefore, the time complexity is proportional to the sum of the lengths of the two strings, resulting in O(n + m).

Space Complexity

O(1) – The algorithm utilizes a constant amount of extra space. It only uses a few integer variables to track the current position in both the 'name' and 'typed' strings. These variables do not scale with the size of the input strings, therefore the auxiliary space complexity is O(1).

Optimal Solution

Approach

The key idea is to compare the typed name and the original name character by character, checking for long presses. We walk through both names at the same time, handling cases where characters are repeated (long pressed) in the typed name.

Here's how the algorithm would work step-by-step:

Start by looking at the first character of both the original name and the typed name.
If the characters match, move to the next character in both names.
If the characters don't match, check if the previous character in the typed name is the same as the current character. If it is, this means the character was long pressed, so we move to the next character in the typed name but stay on the same character in the original name.
If the characters don't match and it's not a long press (the previous typed character isn't the same), then the typed name is incorrect, and we know it's not a valid long press.
Keep going until either the original name or the typed name is finished. If we finish going through the original name and there are still characters left in the typed name, check if they are the same as the last character in the original name (further long presses).
If we finish going through the typed name before the original name, it's not a valid long press because the typed name is missing characters.
If we get through both names using these rules, the typed name is a valid long press of the original name.

Code Implementation

def is_long_pressed_name(name, typed):
    name_index = 0
    typed_index = 0

    while typed_index < len(typed):
        if name_index < len(name) and name[name_index] == typed[typed_index]:
            name_index += 1
            typed_index += 1
        elif typed_index > 0 and typed[typed_index] == typed[typed_index - 1]:
            # This handles long presses of characters in the typed name.
            typed_index += 1

        else:
            return False

    # Ensure all characters in name have been matched.
    if name_index != len(name):
        return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the characters of the original name (let its length be m) and the typed name (let its length be n) using two pointers. In the worst-case scenario, the algorithm iterates through both strings until the end of the longer string is reached. Each pointer advances at most once per character in the strings. Thus the number of operations is bounded by the maximum of m and n. Therefore, the time complexity is O(max(m, n)), which we can simplify to O(n) assuming that the length of the typed name is always greater or equal to the original name.

Space Complexity

O(1) – The algorithm uses only a constant amount of extra space. It uses a few integer variables to keep track of the current positions in the name and typed strings, but the number of such variables is independent of the length of the input strings. Therefore, the auxiliary space used is constant and does not scale with the size of the input names. The space complexity is O(1).

Edge Cases

Case	How to Handle
name is null or empty	Return false immediately as there is nothing to compare against.
typed is null or empty	Return false immediately as there is nothing to compare against.
name is longer than typed	Return false, since 'typed' cannot be a long-pressed version of a longer 'name'.
name and typed are identical	Return true, as 'typed' is a valid long-pressed version of 'name'.
name contains repeating characters at the end, and typed has excessive repetitions of that last character	The main loop and repetition check should properly handle the trailing character repetitions.
typed contains a character that is not in name	Return false, as typed cannot contain characters not present in name.
name contains all same character and typed contains all same character (but different count)	The character counting logic ensures 'typed' contains at least the same number of repeating characters as 'name'.
Consecutive repeated characters in name are not repeated in typed (e.g. name="alex", typed="ale")	Return false, the typed string is missing repetitions of a required character.

name is null or empty

How to Handle:

Return false immediately as there is nothing to compare against.

typed is null or empty

How to Handle:

Return false immediately as there is nothing to compare against.

name is longer than typed

How to Handle:

Return false, since 'typed' cannot be a long-pressed version of a longer 'name'.

name and typed are identical

How to Handle:

Return true, as 'typed' is a valid long-pressed version of 'name'.

name contains repeating characters at the end, and typed has excessive repetitions of that last character

How to Handle:

The main loop and repetition check should properly handle the trailing character repetitions.

typed contains a character that is not in name

How to Handle:

Return false, as typed cannot contain characters not present in name.

name contains all same character and typed contains all same character (but different count)

How to Handle:

The character counting logic ensures 'typed' contains at least the same number of repeating characters as 'name'.

Consecutive repeated characters in name are not repeated in typed (e.g. name="alex", typed="ale")

How to Handle:

Return false, the typed string is missing repetitions of a required character.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can both `name` and `typed` be empty strings, and if so, what should the return value be?
Can `name` or `typed` contain characters other than lowercase letters (e.g., uppercase, numbers, special characters)?
Is it guaranteed that `name` is a valid name and won't have adjacent different characters that are the same (e.g., "aab"), and `typed` similarly is the 'typed' result of a long press of `name`?
If `typed` contains extra characters not present in `name` at all, should I return false?
What is the maximum length of the `name` and `typed` strings?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by comparing the first character of the 'name' with the first character of the 'typed' name.
If they match, move to the next character in both names.
If the characters don't match, check if the current character in 'typed' is the same as the previous character in 'typed'. If it is, we assume it's a long press and move to the next character in 'typed'.
If the characters don't match and the current character in 'typed' is different than the previous character in 'typed', then the 'typed' name can't be a long press of 'name'. Return that it's not possible.
Keep repeating these comparisons until you reach the end of the 'typed' name.
After reaching the end of the 'typed' name, make sure we have also reached the end of the original 'name'. If we haven't, that also means the typed name could not have been generated from the original name.
If we reach the end of both names using these steps, then the 'typed' name is a valid long press of the original 'name'.

Code Implementation

def is_long_pressed_name(name, typed): 
    name_index = 0
    typed_index = 0

    while typed_index < len(typed):
        if name_index < len(name) and name[name_index] == typed[typed_index]:
            name_index += 1
            typed_index += 1

        # Check for long press
        elif typed_index > 0 and typed[typed_index] == typed[typed_index - 1]:
            typed_index += 1

        # If chars don't match and it's not a long press, return False
        else:
            return False

    # Check if we've reached the end of the original name
    if name_index != len(name):
        return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first character of both the original name and the typed name.
If the characters match, move to the next character in both names.
If the characters don't match, check if the previous character in the typed name is the same as the current character. If it is, this means the character was long pressed, so we move to the next character in the typed name but stay on the same character in the original name.
If the characters don't match and it's not a long press (the previous typed character isn't the same), then the typed name is incorrect, and we know it's not a valid long press.
Keep going until either the original name or the typed name is finished. If we finish going through the original name and there are still characters left in the typed name, check if they are the same as the last character in the original name (further long presses).
If we finish going through the typed name before the original name, it's not a valid long press because the typed name is missing characters.
If we get through both names using these rules, the typed name is a valid long press of the original name.

Code Implementation

def is_long_pressed_name(name, typed):
    name_index = 0
    typed_index = 0

    while typed_index < len(typed):
        if name_index < len(name) and name[name_index] == typed[typed_index]:
            name_index += 1
            typed_index += 1
        elif typed_index > 0 and typed[typed_index] == typed[typed_index - 1]:
            # This handles long presses of characters in the typed name.
            typed_index += 1

        else:
            return False

    # Ensure all characters in name have been matched.
    if name_index != len(name):
        return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
name is null or empty	Return false immediately as there is nothing to compare against.
typed is null or empty	Return false immediately as there is nothing to compare against.
name is longer than typed	Return false, since 'typed' cannot be a long-pressed version of a longer 'name'.
name and typed are identical	Return true, as 'typed' is a valid long-pressed version of 'name'.
name contains repeating characters at the end, and typed has excessive repetitions of that last character	The main loop and repetition check should properly handle the trailing character repetitions.
typed contains a character that is not in name	Return false, as typed cannot contain characters not present in name.
name contains all same character and typed contains all same character (but different count)	The character counting logic ensures 'typed' contains at least the same number of repeating characters as 'name'.
Consecutive repeated characters in name are not repeated in typed (e.g. name="alex", typed="ale")	Return false, the typed string is missing repetitions of a required character.

name is null or empty

How to Handle:

Return false immediately as there is nothing to compare against.

typed is null or empty

How to Handle:

Return false immediately as there is nothing to compare against.

name is longer than typed

How to Handle:

Return false, since 'typed' cannot be a long-pressed version of a longer 'name'.

name and typed are identical

How to Handle:

Return true, as 'typed' is a valid long-pressed version of 'name'.

name contains repeating characters at the end, and typed has excessive repetitions of that last character

How to Handle:

The main loop and repetition check should properly handle the trailing character repetitions.

typed contains a character that is not in name

How to Handle:

Return false, as typed cannot contain characters not present in name.

name contains all same character and typed contains all same character (but different count)

How to Handle:

The character counting logic ensures 'typed' contains at least the same number of repeating characters as 'name'.

Consecutive repeated characters in name are not repeated in typed (e.g. name="alex", typed="ale")

How to Handle:

Return false, the typed string is missing repetitions of a required character.

0/1916 Google questions completed

0/1916 completed