Faulty Keyboard

Easy
0/40
profile
Contributed by
3 upvotes
Asked in companies
Morgan StanleyAdobe

Problem statement

Ninja has an old keyboard, which is now a piece of junk, but Ninja still loves it.

There is a major problem with the keyboard, pressing a single key can type the same character multiple times. This sometimes results in incorrect text being typed.

You are given two strings ‘Expected’ and ‘Typed’, you need to tell if the actual text was typed correctly or not. The text is typed correctly if some characters were long pressed (typed multiple times) while typing the ‘Expected’ text. Print “true” if the actual text was typed correctly, else print “false”.

For Example : 
If Typed = “aaabcc” and Expected = “abc”

Then, while trying to type “abc” one might long press ‘a’ and that would result in typing three consecutive a’s. This if followed by correctly pressing ‘b’ once and in the end he might long press ‘c’ resulting in typing it twice, the resulting text typed in this case is equal to “aaabcc” and therefore we will return “true”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a string ‘Expected’ that denotes the original text that was to be typed.

The second line of each test case contains a string ‘Typed’ that denotes the text that was actually typed.
Output Format : 
For each test case, print the “true” if the text was typed correctly, else print “false”.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10      
1 ≤ |Expected| ≤ 5000
1 ≤ |Typed| ≤ 5000
Both the strings consist of lowercase English alphabets 

Time limit: 1 sec
Sample Input 1 :
2
abc
aaabcc
abcd
aaabdcc
Sample Output 1 :
true
false
Explanation For Sample Input 1 :
For test case 1 :
The text was typed correctly because:
While trying to type “abc” one might long-press ‘a’ and that would result in typing three consecutive a’s. This if followed by correctly pressing ‘b’ once and in the end one might long-press ‘c’ resulting in typing it twice, the resulting text typed in this case is equal to “aaabcc” and therefore we will return “true”.

For test case 2 : 
The text was typed incorrectly because:
While trying to type “abcd”, one cannot type “aaabdcc” as the faulty keyboard may cause typing a character multiple times, but it cannot cause typing the character ‘d’ of the original text before the character ‘c’, the ‘Typed’ text has ‘d’ before ‘c’, which means the text was typed incorrectly, therefore we will return “false”.
Sample Input 2 :
2
abccc
aaabcc
z
zzzzzz
Sample Output 2 :
false
true
Hint

Try using two pointers, one pointer for each string and try to check if the text was typed correctly or not!

Approaches (1)
Two pointer

Initialize two pointers to point to the beginning of each string. Run a while loop, check if both the pointers point to the same characters or not, in case they point to different characters then return “False” as this is the case when it is not possible to match the strings as a different character is typed or the order in which characters were typed is different. If the current characters pointed by both the pointers match then run a while loop to take increase the pointer pointing the ‘Typed’ text if needed to consider the condition of using the faulty keyboard. Break the outer while loop if both the pointers point to the end of their respective strings and return “True” as this will denote that we have matched the condition of the faulty keyboard. In case only one of the pointers points to the end of its string then return “False” as this is the case when we might have pressed some extra incorrect keys in the end or might have pressed fewer keys than that were actually to be pressed for typing the text.

 

The steps are as follows :

  1. Initialize two pointers ‘pt1’ and ‘pt2’ and set their values equal to 0. We will use these pointers to iterate through the strings, ‘pt1’ will iterate through the ‘Expected’ string and ‘pt2’ will iterate through the ‘Typed’ string.
  2. Run a while loop, inside the loop check:
    • If both the pointers point to the ends of their respective strings, if found then return “True”
    • If not, then check if one of them points to the end of its string, if found then return “False”.
    • Else check if both the pointers point to the equal characters or not, if they point to different characters then return “False”. If it points to equal characters then, increment the value of both the pointer by one unit.
    • Now run an inner while loop to take into account the condition of the faulty keyboard, run this while loop till ‘pt2’ doesn’t point to the end and till the characters at position Typed[pt2] and Typed[pt2 - 1] are equal.
    • Increment the value of ‘pt2’ inside this while loop till the above-mentioned conditions are true.
Time Complexity

O( N + M ), where N and M denote the length of the ‘Expected’ and ‘Typed’ strings.

 

In the worst case, when the original text was typed correctly, we end up iterating through each character of both the strings exactly once.

Hence the time complexity is O( N+M ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Faulty Keyboard
Full screen
Console