Check if a String is the Typed Name of the Given Name in Java
In this tutorial, we are going to check if a string is the typed name of the given name in Java. Given the typed version of the person's name. Sometimes the key may be prolonged when typing the vowel [aeiou], causing the character to be typed one or more times. The aim is to look at the typed name and see if it seems like a person's name with some or all of the characters being long pressed. In that case, give back "True," else "False." The individual's name and the typed name are separated by no space. Each character in the name is unique.
Examples:
Example 1:
Input: string = “brain”, typed = “brraiaann”
Output: false
Explanation: Because the characters "r," "a," and "n" are not vowels and are repeated more frequently than in the original name, the typed name "brraiaann" in this instance does not accurately reflect the original name "brian." Thus, the result would be false.
Approach 1: Using run length encoding
ALGORITHM:
Step 1: Contemplate only vowels.
Step 2: Sort and count the number of times they appear in a row.
Step 3: Occurrences in string count must be less.
Filename: TypedName.java
public class TypedName
{
// Check whether the character is a vowel or not
static boolean isVowel(char character)
{
String vowels = "aeiou";
for (int i = 0; i < vowels.length(); ++i)
if (vowels.charAt(i) == character)
return true;
return false;
}
// Given original string returns true if 'typed' is a typed name.
static boolean printRunLengthEncoding(String originalName, String typedName)
{
int x = originalName.length(), y = typedName.length();
int a = 0, b = 0;
for (a = 0; a < x; a++)
{
if (originalName.charAt(a) != typedName.charAt(b))
return false;
if (isVowel(originalName.charAt(a)) == false)
{
b++;
continue;
}
// Determine how many times the current vowel occurs in the string.
int nameVowelCount1 = 1;
while (a < x - 1 && originalName.charAt(a) == originalName.charAt(a + 1))
{
nameVowelCount1++;
a++;
}
int nameVowelCount2 = 1;
while (b < y - 1 && typedName.charAt(b) == originalName.charAt(a))
{
nameVowelCount2++;
b++;
}
if (nameVowelCount1 > nameVowelCount2)
return false;
}
return true;
}
public static void main(String args[])
{
String originalName = "alice", typedName = "aaalicce";
if (printRunLengthEncoding(originalName, typedName))
System.out.println("Yes");
else
System.out.println("No");
}
}
Output:
No
Complexity analysis:
Time complexity:
The time complexity of the program is O(m + n).
Space complexity:
The space complexity of the program is O(1).
Approach 2: Using two pointers
ALGORITHM:
Step 1: First, we initialize two pointers: one for the typed string (j) and another for iterating through the characters in the name string (i).
Step 2: Compare the characters at their current places while we simultaneously go through both strings.
Step 3: Advance both pointers to the following character in their respective strings if the characters match. If they don't match, we see if the character being typed right now and the character before it match.
Step 4: Go to the next character that is typed if it does. We return false otherwise. This procedure is carried out until we get to the end of either string.
Step 5: Make sure that all characters typed after going through both strings are duplicates of the previous character.
Step 6: Return true if we are able to successfully traverse both strings and there are no more characters; if not, we return false. Although it offers a fundamental solution to the issue, this strategy might not be as effective as optimized ones.
Filename: CharacterPressed.java
public class CharacterPressed
{
public static void main(String[] args)
{
CharacterPressed twopointers = new CharacterPressed();
System.out.println(twopointers.isLongPressedName("alice", "aalicce")); System.out.println(twopointers.isLongPressedName("sayed", "ssaayedd")); System.out.println(twopointers.isLongPressedName("lilly", "lliiily"));
System.out.println(twopointers.isLongPressedName("laiden", "laiden"));
}
public boolean isLongPressedName(String originalName, String typedName)
{
int typedInd = 0;
int typedLength = typedName.length();
int nameLength = originalName.length();
for (int a = 0; a < nameLength; a++, typedInd++)
{
if (typedInd >= typedLength || originalName.charAt(a) != typedName.charAt(typedInd))
return false;
while (typedInd + 1 < typedLength && typedName.charAt(typedInd) == typedName.charAt(typedInd + 1))
{
typedInd++;
}
}
return typedInd == typedLength;
}
}
Output:
true true false true
Complexity analysis:
Time complexity:
The time complexity of the program is O(n).
Space complexity:
The space complexity of the program is O(1).