925. Long Pressed Name

EasyTwo PointersString
Leetcode Link

Problem Description

The problem presents a scenario where your friend is typing his name on a keyboard, but some characters might get typed more than once due to the key getting long-pressed. Your task is to determine if the typed string of characters could represent the actual name of your friend, even with some characters potentially being repeated due to long presses. In other words, you need to verify if the typed string is a valid representation of the actual name with the allowance for extra characters that are the result of long presses.

For example, if your friend's name is "alex" and the typed string is "aaleex", the function should return True because the extra "a" and "e" could result from long pressing those keys. However, if the typed string is "aaleexa", the function should return False because the 'a' at the end of the typed string cannot be accounted for by a long press when typing "alex".

Intuition

The intuition behind the solution is to traverse both the name and the typed strings and compare them character by character. We start by initializing two pointers, one for each string. As we progress through both strings:

  • If the current characters don't match, it's clear that typed does not match name, and we return False.
  • If the characters match, we then need to count the subsequent occurrences of that character in both strings to ensure that the typed string does not contain fewer repetitions of the character than the name string (which would be invalid).

To implement this, we count the number of times the current character appears consecutively in both the name and typed strings. If the count in name is greater than in typed, then the typed string cannot be the result of long pressing while typing name, and we return False.

If we complete the traversal without encountering any discrepancies, we then make sure that both pointers have reached the ends of their respective strings. This final check ensures that there aren't any extra characters in the typed string that don't match with the name. If both pointers are at the end, we return True; otherwise, we return False.

The approach makes use of a two-pointer technique to compare the strings efficiently, checking character by character to verify the validity of the long-pressed string.

Learn more about Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following array represent a max heap?

Solution Approach

The provided solution implements a two-pointer technique. Two pointers, i and j, are used to iterate through the name and typed strings respectively. The approach utilizes the fact that for typed to be a result of long-pressing the keys while typing name, every character in name must appear in typed in the same order and there must be at least the same number of each character in typed as there is in name.

Here's the step-by-step breakdown of the algorithm:

  1. Initialize two variables, i and j, to 0. These will serve as pointers to iterate through name and typed.
  2. Loop through the strings while i < m and j < n, where m is the length of name and n is the length of typed. This will ensure that we are comparing the characters within the bounds of both strings.
  3. If at any point, the characters at the current pointers name[i] and typed[j] do not match, we return False as this immediately disqualifies the typed string from being a valid representation of name caused by long pressing.
  4. If the characters match, we then count the consecutive appearances of the current character c = name[i] in both strings. This is done by looping while the next character is the same as c and incrementing cnt1 or cnt2 for name and typed respectively.
  5. After counting the appearances, if cnt1 (the count for name) is greater than cnt2 (the count for typed), we return False because typed has fewer characters than required.
  6. Both pointers are then moved to the next character (i + 1 and j + 1), and steps 3-5 are repeated until one of the strings is fully traversed.
  7. Finally, we check if both i and j have reached the end of their respective strings (i == m and j == n). If they have, this means typed could indeed be a long-pressed version of name, so we return True. If not, then typed contains additional characters not found in name, and we return False.

No additional data structures are used in this approach. All that is needed are a few variables to keep track of positions within the strings and the counts of the consecutive characters. The solution's correctness relies on the ordered comparison of characters and the counts of consecutive occurrences, which align with the rules of how arrays (strings) are constructed and the problem's constraints regarding long presses.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's use a small example to illustrate the solution approach. Assume your friend's name is "sara" and the typed string is "ssaarraa". We'll walk through the algorithm to determine if "ssaarraa" could be a long-pressed version of "sara".

  1. Initialize two pointers i and j to 0.
  2. As long as i < len(name) and j < len(typed), proceed to compare the characters.

At the beginning:

  • i = 0, name[i] = 's'
  • j = 0, typed[j] = 's'
  1. Both characters match, so we start counting consecutive characters in both strings.

In name:

  • i = 0 to i = 1, the character changes from 's' to 'a', so cnt1 for 's' in name is 1.

In typed:

  • j = 0 to j = 1, 's' is repeated, and at j = 2, it changes to 'a', so cnt2 for 's' in typed is 2.
  1. Since cnt1 <= cnt2, we proceed.
  2. Move both pointers to the next set of characters and repeat steps 2-4.

Now:

  • i = 1, name[i] = 'a'
  • j = 2, typed[j] = 'a'

We repeat the counting:

  • i moves from 1 to 2, encountering 'r', so cnt1 for 'a' is 1 in name.
  • j moves from 2 to 4, with 'a' at indices 2 to 3 before we find 'r', so cnt2 for 'a' is 2 in typed.

Again, cnt1 <= cnt2, so we proceed. Continue this process for each character in name.

After completing the traversal:

  • We reach i = 4 (i == len(name)), indicating we've checked all characters in name.
  • Similarly, we reach j = 8 (j == len(typed)), indicating all characters in typed have been accounted for.
  1. Since we have successfully gone through both strings without finding a mismatch or insufficient count of characters in typed, and both pointers have reached the end of their respective strings, the function will return True. "ssaarraa" is a valid long-pressed version of "sara".

Solution Implementation

1class Solution:
2    def isLongPressedName(self, name: str, typed: str) -> bool:
3        # Lengths of the input strings
4        name_length = len(name)
5        typed_length = len(typed)
6      
7        # Initialize pointers for name and typed
8        name_index = typed_index = 0
9      
10        # Loop through both strings simultaneously
11        while name_index < name_length and typed_index < typed_length:
12          
13            # If characters at current position do not match, return False
14            if name[name_index] != typed[typed_index]:
15                return False
16          
17            # Count occurrences of the current character in both strings
18            count_name = count_typed = 0
19            current_char = name[name_index]
20          
21            # Count consecutive characters in name
22            while name_index + 1 < name_length and name[name_index + 1] == current_char:
23                name_index += 1
24                count_name += 1
25          
26            # Count consecutive characters in typed
27            while typed_index + 1 < typed_length and typed[typed_index + 1] == current_char:
28                typed_index += 1
29                count_typed += 1
30          
31            # If name has more consecutive characters than typed, return False
32            if count_name > count_typed:
33                return False
34          
35            # Move to the next character
36            name_index += 1
37            typed_index += 1
38      
39        # Check if both strings have been fully traversed
40        return name_index == name_length and typed_index == typed_length
41
1class Solution {
2    public boolean isLongPressedName(String name, String typed) {
3        int nameLength = name.length();
4        int typedLength = typed.length();
5        int nameIndex = 0, typedIndex = 0;
6
7        // Iterate over each character in both strings
8        while (nameIndex < nameLength && typedIndex < typedLength) {
9            // If the current characters don't match, return false
10            if (name.charAt(nameIndex) != typed.charAt(typedIndex)) {
11                return false;
12            }
13
14            // Count consecutive characters in the original name
15            int nameCharCount = 0;
16            char currentChar = name.charAt(nameIndex);
17            while (nameIndex + 1 < nameLength && name.charAt(nameIndex + 1) == currentChar) {
18                nameIndex++;
19                nameCharCount++;
20            }
21
22            // Count consecutive characters in the typed string
23            int typedCharCount = 0;
24            while (typedIndex + 1 < typedLength && typed.charAt(typedIndex + 1) == currentChar) {
25                typedIndex++;
26                typedCharCount++;
27            }
28
29            // If the original name has more consecutive characters than the typed one, return false
30            if (nameCharCount > typedCharCount) {
31                return false;
32            }
33
34            // Move to the next character
35            nameIndex++;
36            typedIndex++;
37        }
38
39        // If we have reached the end of both strings, the name is correctly typed
40        return nameIndex == nameLength && typedIndex == typedLength;
41    }
42}
43
1class Solution {
2public:
3    bool isLongPressedName(string name, string typed) {
4        int nameLength = name.size(), typedLength = typed.size();
5        int nameIndex = 0, typedIndex = 0;
6
7        // Iterate through each character of both strings
8        for (; nameIndex < nameLength && typedIndex < typedLength; ++nameIndex, ++typedIndex) {
9            // If the characters don't match, return false
10            if (name[nameIndex] != typed[typedIndex]) return false;
11
12            int nameCharCount = 0, typedCharCount = 0; // Counters for the occurrences of the current character
13            char currentChar = name[nameIndex];
14
15            // Count consecutive occurrences in `name`
16            while (nameIndex + 1 < nameLength && name[nameIndex + 1] == currentChar) {
17                ++nameIndex;
18                ++nameCharCount;
19            }
20            // Count consecutive occurrences in `typed`
21            while (typedIndex + 1 < typedLength && typed[typedIndex + 1] == currentChar) {
22                ++typedIndex;
23                ++typedCharCount;
24            }
25            // If `name` has more consecutive characters than `typed`, the typing is not long-pressed
26            if (nameCharCount > typedCharCount) return false;
27        }
28
29        // Check that we have iterated through both strings completely
30        return nameIndex == nameLength && typedIndex == typedLength;
31    }
32};
33
1function isLongPressedName(name: string, typed: string): boolean {
2    let nameLength = name.length, typedLength = typed.length;
3    let nameIndex = 0, typedIndex = 0;
4
5    // Iterate through each character of 'name' and 'typed' simultaneously
6    for (; nameIndex < nameLength && typedIndex < typedLength; nameIndex++, typedIndex++) {
7        // If the characters at the current position do not match, it's not long-pressed
8        if (name[nameIndex] !== typed[typedIndex]) {
9            return false;
10        }
11
12        let nameCharCount = 0, typedCharCount = 0; // Counters for occurrences of the current character
13        let currentChar = name[nameIndex];
14
15        // Count the consecutive occurrences of the current character in 'name'
16        while (nameIndex + 1 < nameLength && name[nameIndex + 1] === currentChar) {
17            nameIndex++;
18            nameCharCount++;
19        }
20
21        // Count the consecutive occurrences of the current character in 'typed'
22        while (typedIndex + 1 < typedLength && typed[typedIndex + 1] === currentChar) {
23            typedIndex++;
24            typedCharCount++;
25        }
26
27        // If 'name' has more consecutive characters than 'typed', it's not long-pressed
28        if (nameCharCount > typedCharCount) {
29            return false;
30        }
31    }
32
33    // Check that both strings have been fully iterated through
34    return nameIndex === nameLength && typedIndex === typedLength;
35}
36
37// You can call isLongPressedName with actual parameters like so:
38// const result = isLongPressedName("alex", "aalleex"); // This should return true
39
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the typed string. This is because the two pointers i and j, which iterate over name and typed strings, can only move forward and each character in both strings will be visited at most once.

The space complexity of the code is O(1) because there are a fixed number of variables used and their space requirement does not scale with the input size. No additional data structures or dynamic memory allocation is used in this code that would make the space complexity scale with input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫