Long Pressed Name - Leetcode Solution

Problem statement: You are given a string name and a string typed. You need to determine if typed is a string that has been generated by long pressing name.

A long press means that you have pressed a key for a longer duration than usual which results in the character of the key being typed multiple times.

Constraints:

1 <= name.length <= 1000 1 <= typed.length <= 1000 name and typed contain only lowercase English letters.

Example 1: Input: name = "alex", typed = "aaleex" Output: true Explanation: 'a' and 'e' are repeated in typed.

Example 2: Input: name = "saeed", typed = "ssaaedd" Output: false Explanation: In typed, 'e' is repeated but not in name.

Approach/Algorithms: The approach to solving the problem would involve two pointers: one for traversing the name string and another for traversing the typed string. We will traverse through both the strings and compare the characters at the current positions of both the pointers. If they match, we will increment both pointers, otherwise we will check if the current character of the typed string is the same as the previous character of the typed string. If it is, we will only increment the pointer of the typed string, otherwise we will return false.

Solution:

class Solution { public boolean isLongPressedName(String name, String typed) { int i = 0, j = 0; while (i < name.length() && j < typed.length()) { if (name.charAt(i) == typed.charAt(j)) { i++; j++; } else if (j > 0 && typed.charAt(j) == typed.charAt(j - 1)) { j++; } else { return false; } } while (j < typed.length() && typed.charAt(j) == typed.charAt(j - 1)) { j++; } return i == name.length() && j == typed.length(); } }

Time Complexity: O(n) Space Complexity: O(1)

Explanation: We use two pointers i and j to traverse through the name and typed strings respectively. We check if the ith character of name and jth character of typed are the same. If they are, we increment both the pointers. If they are not, we check if the jth character of typed is equal to the previous character of typed, i.e., j > 0 and typed.charAt(j) == typed.charAt(j-1). In this case, we increment j only since it is long pressed. If the jth character of typed is not equal to the previous character of typed and is also not equal to the ith character of name, we return false since it means that the typed string is not generated by long pressing the name string.

After we have traversed through both the strings, we need to check if there are any long-pressed characters left in the typed string. For this, we check if there are any characters in typed beyond the current position of j which are equal to the previous character. If there are such characters, we increment j until we find a character which is not equal to the previous character. If there are no such long-pressed characters left in typed, we check if we have reached the end of both the strings. If both the pointers i and j are at the end of their respective strings, it means that typed is a string that has been generated by long pressing name, so we return true. Otherwise, we return false.

This is how we solve the Long Pressed Name problem in Java on LeetCode.

1