925. Long Pressed Name
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 matchname
, and we returnFalse
. - 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 thename
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.
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:
- Initialize two variables,
i
andj
, to 0. These will serve as pointers to iterate throughname
andtyped
. - Loop through the strings while
i < m
andj < n
, wherem
is the length ofname
andn
is the length oftyped
. This will ensure that we are comparing the characters within the bounds of both strings. - If at any point, the characters at the current pointers
name[i]
andtyped[j]
do not match, we returnFalse
as this immediately disqualifies thetyped
string from being a valid representation ofname
caused by long pressing. - 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 asc
and incrementingcnt1
orcnt2
forname
andtyped
respectively. - After counting the appearances, if
cnt1
(the count forname
) is greater thancnt2
(the count fortyped
), we returnFalse
becausetyped
has fewer characters than required. - Both pointers are then moved to the next character (
i + 1
andj + 1
), and steps 3-5 are repeated until one of the strings is fully traversed. - Finally, we check if both
i
andj
have reached the end of their respective strings (i == m and j == n
). If they have, this meanstyped
could indeed be a long-pressed version ofname
, so we returnTrue
. If not, thentyped
contains additional characters not found inname
, and we returnFalse
.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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".
- Initialize two pointers
i
andj
to 0. - As long as
i < len(name)
andj < len(typed)
, proceed to compare the characters.
At the beginning:
i = 0
,name[i] = 's'
j = 0
,typed[j] = 's'
- Both characters match, so we start counting consecutive characters in both strings.
In name
:
i = 0
toi = 1
, the character changes from 's' to 'a', socnt1
for 's' inname
is 1.
In typed
:
j = 0
toj = 1
, 's' is repeated, and atj = 2
, it changes to 'a', socnt2
for 's' intyped
is 2.
- Since
cnt1 <= cnt2
, we proceed. - 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', socnt1
for 'a' is 1 inname
.j
moves from 2 to 4, with 'a' at indices 2 to 3 before we find 'r', socnt2
for 'a' is 2 intyped
.
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 inname
. - Similarly, we reach
j = 8
(j == len(typed)
), indicating all characters intyped
have been accounted for.
- 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 returnTrue
. "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
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.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe 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 div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!