A simple DP approach works. For example, a = "aBbdD" b = "BBD" since the last character in a is upper case and last character in b is also upper case and both are equal, f(a,b) = f("aBbd","BB")

Now d can never be made equal to B therfore- f("aBbd","BB") = f("aBb","BB")

Now b can be capitalized to B,therfore we have two options - either capitalize b to B or dont capitalize b. f("aBb","BB") = f("aB","B") or f("aB","BB") #Note that this is the 'or' operator. f is a boolean value.

if we have something like a = 'C' and b = 'D' then f(a,b) evaluates to False (boolean value).

Lastly (for initialization of the dp array)-

if a is non-empty and b is empty, then f(a,b) is True only if all the characters in a are lower case.

if a is empty and b is non-empty, then f(a,b) is always False.

if both are empty then f(a,b) = True

Good Luck !!

Useful test cases that was generated by my test driver which helped me pass all the test cases:

ababbaAbAB AABABB false

aAbAb ABAB true

baaBa BAAA false

abAAb AAA true

babaABbbAb ABAA false

Took a while but I finally got it. My python solution:

def abbreviation(a, b):
    m, n = len(a), len(b)
    dp = [[False]*(m+1) for _ in range(n+1)]
    dp[0][0] = True
    for i in range(n+1):
        for j in range(m+1):
            if i == 0 and j != 0:
                dp[i][j] = a[j-1].islower() and dp[i][j-1]
            elif i != 0 and j != 0:
                if a[j-1] == b[i-1]:
                    dp[i][j] = dp[i-1][j-1]
                elif a[j-1].upper() == b[i-1]:
                    dp[i][j] = dp[i-1][j-1] or dp[i][j-1]
                elif not (a[j-1].isupper() and b[i-1].isupper()):
                    dp[i][j] = dp[i][j-1]
    return "YES" if dp[n][m] else "NO"

I spent a few days thinking about the problem and wanted to give some tips to those learning about dynamic programming.

1. Try to first solve it recursively with small sample cases and then try to apply memoization. Do not start thinking about the dynamic approach because I got lost doing that and was not sure how to apply a single base case.
2. If you do it bottom up in Python try to optimize it because it might time out (mine did on the last 2 cases).
3. Try doing it with True and False as the values of the DP table, this way you don't have to think about numbers and edit distances and stuff.

Hope this helps!

What we need to solve is, regardless of the case, if b is a subsequence of a with the constraint that a can only discard lower case characters. Therefore, if we want to know if b[0, i] is an abbreviation of a[0, j], we have two cases to consider:

1. a[j] is a lower case character.

if uppercase(a[j]) == b[i], either b[i - 1]is an abbreviation of a[0, j - 1] or b[i - 1] is an abbreviation of a[0, j], b[0, i] is an abbreviation of a[0, j].

else if b[0, i] is an abbreviation of a[0, j -1], b[0, i] is an abbreviation of a[0, j].

else, b[0, i] cannot be an abbreviation of a[0, j].

2. a[j] is a upper case character.

if a[j] == b[i] and b[0, i - 1] is an abbreviation of a[0, j - 1], b[0, i] is an abbreviation of a[0, j].

else b[0, i] cannot be an abbreviation of a[0, j].

Below is a Java solution:

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the abbreviation function below.
    static String abbreviation(String a, String b) {
        boolean[][] dp = new boolean[b.length() + 1][a.length() + 1];
        dp[0][0] = true;
        for (int j = 1; j < dp[0].length; j++) {
            if (Character.isLowerCase(a.charAt(j - 1))) dp[0][j] = dp[0][j - 1];
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                char ca = a.charAt(j - 1), cb = b.charAt(i - 1);
                if (ca >= 'A' && ca <= 'Z') {
                    if (ca == cb) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }else {
                    ca = Character.toUpperCase(ca);
                    if (ca == cb) dp[i][j] = dp[i - 1][j - 1] || dp[i][j - 1];
                    else dp[i][j] = dp[i][j - 1];
                }
            }
        }
        
        return dp[b.length()][a.length()] ? "YES" : "NO";
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int qItr = 0; qItr < q; qItr++) {
            String a = scanner.nextLine();

            String b = scanner.nextLine();

            String result = abbreviation(a, b);

            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}