Abbreviation — HackerRank Medium

Here is the link to the problem.

This problem requires us to check if string a can be converted to string b in the following conditions.

1. Capitalize zero or more of a’s lower case letters
2. Delete lowercase letters

Keep in mind that we cannot change any characters, or insert any characters. Also an implied 3rd condition or could also cal it a hint is that if there is a UpperCase in a character which is not in b, we have an invalid string because it cannot be deleted.

For example the string daBcd is equal to ABC because both d can be removed while we can convert the lowercase a and c to uppercase to match b.

But daBcD is not equal to ABC because the uppercase D cannot be removed.

We will use dynamic programming to solve this problem.

There are basically 4 different conditions that we need to keep in mind while solving this problem.

1. The character in a is equal to character in b
2. The character in a when changed to upper case is equal to character in b
3. The character in a is upper case and not equal to character in b
4. The character in a is lower case but not equal to character in b

Basically, if the character is uppercase and a match we look at the diagonal value because that character does not break the validity of the string, and if the last character also did not which is at diagonal (i-1, j-1) then we make it True.

If lowercase character matches when changed to upper case we look either diagonal or top. We look at diagonal for the same reason as earlier but we look at top because, we can simply delete this character and thus if either or left diagonal is True we set this to True.

If it is uppercase and not match we just simply leave it as false because it breaks validity.

Else, we look at left.

The dynamic array is filled up in the follow manner. Note: We initialize our dp array with lengths of word + 1 to accommodate empty values.

And we initialize the [i][0] values(the first column) to be T if the character at that index is a small character since we can remove it and make it equal to the empty array of value b.

In code:
if (a.charAt(i-1) == b.charAt(j-1)) {
   isValid[i][j] = isValid[i-1][j-1];
}else if (Character.toUpperCase(a.charAt(i-1))  ==  b.charAt(j-1)) {
   isValid[i][j] = isValid[i-1][j-1] || isValid[i-1][j];
}else if (Character.isUpperCase(a.charAt(i-1))) {
   isValid[i][j] = false;
}else {
   isValid[i][j] = isValid[i-1][j];
}
The last element of the array is our answer. This plays out in this manner.

How the array looks like.

The full solution would look like:

boolean[][] isValid = new boolean[a.length()+1][b.length()+1];
isValid[0][0] = true;
for (int i= 1; i <= a.length(); i++) {
   if (Character.isUpperCase(a.charAt(i - 1))) {
      isValid[i][0] = false;
   }
   else isValid[i][0] = true;
}
for (int i = 1; i <= a.length(); i++) {
   for (int j = 1; j <= b.length(); j++) {
      if (a.charAt(i-1) == b.charAt(j-1)) {
      isValid[i][j] = isValid[i-1][j-1];
      }else if (Character.toUpperCase(a.charAt(i-1))  ==    b.charAt(j-1)) {
         isValid[i][j] = isValid[i-1][j-1] || isValid[i-1][j];
      }else if (Character.isUpperCase(a.charAt(i-1))) {
         isValid[i][j] = false;
      }else {
         isValid[i][j] = isValid[i-1][j];
      }
   }
}
return isValid[a.length()][b.length()]? "YES" : "NO";

Thank you for reading! Please comment any questions you might have.

Here is the video explanation.