algoadvance

Leetcode 925. Long Pressed Name

Problem Statement

Suppose your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character might be typed one or more times.

You examine the typed characters of the keyboard. Return True if it is possible that it was your friend’s 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 wasn't in the typed output.

Example 3:

Input: name = "leelee", typed = "lleeelee"
Output: true

Constraints:

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

Clarifying Questions

1. Are the input strings guaranteed to be non-empty?
   • Yes, as per the constraints.
2. Can we assume that both name and typed will only contain lowercase English letters?
   • Yes, as per the constraints.

Strategy

We can solve this problem using a two-pointer technique. The idea is to iterate through both strings simultaneously, comparing characters and handling long presses as needed.

1. Use two pointers, i for name and j for typed.
2. Iterate through the typed string with pointer j:
   • If the character at typed[j] matches the character at name[i], move both pointers i and j forward.
   • If they don’t match, then check if typed[j] matches typed[j-1] (indicating a long press). If it does, only move j forward.
   • If neither condition holds, return false because the strings don’t match the criteria.
3. After the loop, check if we have traversed the entire name (i.e., i == name.length()).

Code

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int i = 0, j = 0;
        while (j < typed.length()) {
            if (i < name.length() && name[i] == typed[j]) {
                i++;
                j++;
            } else if (j > 0 && typed[j] == typed[j - 1]) {
                j++;
            } else {
                return false;
            }
        }
        return i == name.length();
    }
};

Time Complexity

• The time complexity for this solution is O(n), where n is the length of the typed string. This is because each character in typed is processed at most once.
• The space complexity is O(1) since we are using only a few extra variables.

This approach ensures that we efficiently check if typed can be derived from name considering the long press scenario.

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?