Transform String a into b

Question

You can perform the following operation on some string a:

1. Capitalize zero or more of a's lowercase letters at some index i (i.e., make them uppercase).

2. Delete all of the remaining lowercase letters in a.

Given string a, print YES if it can be transformed to string b.

String a has only capital and small letter alphabets.

String b has only capital letters.

THIS is the link to the problem.

Example:

a: daBcd

b: ABC

OUTPUT: YES

This passed all the test-cases. But I wanted to know if any further optimizations can be made or not. Maybe I am using redundant conditions or something like this.

 //n is the length of the string a
 //m is the length of the string b
 public static void func(char[] a,int n, char[] b, int m)
    {
        int[][] mat = new int[n + 1][m + 1];
        for(int i = 0 ; i < n + 1 ; i++)
            mat[i][0] = 0;
        for(int i = 0 ; i < m + 1 ; i++)
            mat[0][i] = 0;
        char capStart = 65;
        char capEnd = 90;
        char smallStart = 97;
        char smallEnd = 122;
        char diff = 32;
        for(int i = 1 ; i < n + 1 ; i++)
        {
            for(int j = 1 ; j < m + 1 ; j++)
            {
                if(a[i - 1] >= smallStart)
                {
                    if(a[i - 1] - diff == b[j - 1])
                    {
                        if(mat[i - 1][j] == j)
                            mat[i][j] = mat[i - 1][j];
                        else
                            mat[i][j] = 1 + mat[i - 1][j - 1];
                    }
                    else
                    {
                        if(mat[i - 1][j] == j || mat[i][j - 1] == j)
                            mat[i][j] = j;
                        else
                            mat[i][j] = Math.max(mat[i - 1][j],mat[i][j - 1]);
                    }
                }
                else
                {
                    if(a[i - 1] == b[j - 1])
                    {
                        mat[i][j] = 1 + mat[i - 1][j - 1];
                    }
                    else
                    {
                        mat[i][j] = mat[i][j - 1];
                    }
                }
            }
        }
        if(mat[n][m] == m)
            System.out.println("YES");
        else
            System.out.println("NO");
    }

If you want, you can check your solution for 1 of the sample inputs:

Input format:

First line contains an integer q showing the number of pairs of a and b. Next 2q lines for a and b.

10
Pi
P
AfPZN
APZNC
LDJAN
LJJM
UMKFW
UMKFW
KXzQ
K
LIT
LIT
QYCH
QYCH
DFIQG
DFIQG
sYOCa
YOCN
JHMWY
HUVPW 

Output:

YES
NO
NO
YES
NO
YES
YES
YES
NO
NO

Answer 1

        int[][] mat = new int[n + 1][m + 1];
        for(int i = 0 ; i < n + 1 ; i++)
            mat[i][0] = 0;
        for(int i = 0 ; i < m + 1 ; i++)
            mat[0][i] = 0;

Consider

        int[][] mat = new int[n + 1][m + 1];
        Arrays.fill(mat[0], 0);
        for (int i = 1; i < mat.length; i++) mat[i][0] = 0;

Now we no longer initialize mat[0][0] twice. We initialize it only once because we exclude it from the for loop.

We use the built-in to initialize the first row.

We initialize the rest of the first column with a for loop, as the built-in doesn't work with columns.

Since we are using the single statement version of the for loop, we put the single statement on the same line as the for loop. Now it's obvious that it's just a single statement. Before it was less obvious.

I would actually prefer to always use the block form, but that's your choice.

I changed from n + 1 to mat.length because it is more robust in the face of future changes. Consider what happens if you were to change the n + 1 in the first line to n + 2. In the original code, you would have to change the second line as well. In this version, you don't.

One might argue that you would never change the 1 to a 2 in this code. But even if that is so here, that might not be true in other code. It is a good habit to try to avoid having code parallel other code. If possible, make the code follow the other as it does here. The mat.length will always be the right value here while the n + 1 is dependent on the logic used now.

I'm not crazy about the name mat. I'm guessing it's short for matrix, but matrix of what? It seems like there could be a more descriptive name.

Note that given the way that Java defaults integer values, the initialization is actually unnecessary. Java will initialize the whole thing to 0. You don't have to do any explicit initialization. Java will do what you want automatically.

        char capStart = 65;
        char capEnd = 90;
        char smallStart = 97;
        char smallEnd = 122;
        char diff = 32;

You only use two of these

        char smallStart = 'a';
        char diff = 'A' - 'a';

I find this more readable. By substituting 'a' for the numeric value, it is clearer about what we seek. Although I'd probably just change

                if(a[i - 1] >= smallStart)

to

                if (a[i - 1] >= 'a')

or

                if (Character.isLowerCase(a[i - 1]))

That last may be longer, but it is also more robust against other alphabets than the latin1 alphabet. And it may be better optimized as well.

        for(int i = 1 ; i < n + 1 ; i++)
        {
            for(int j = 1 ; j < m + 1 ; j++)

Given the frequency with which you say i - 1 and j - 1, I'd consider saying

        for (int i = 0; i < a.length; i++)
        {
            for (int j = 0; j < b.length; j++)

I believe that this reads more naturally. For each letter in a and for each letter in b, do...

Don't forget to change all the i - 1 to i and all the i to i + 1 if you do this.

Answer 2

The algorithm you chose is both complicated and slow. There is a much easier idea that should solve the task:

import static org.assertj.core.api.Assertions.assertThat;

import org.junit.Test;

public class Cr181050 {

    static boolean canBeConverted(String source, String target) {
        int slen = source.length();
        int tlen = target.length();

        int ti = 0;   // target index
        for (int si = 0; si < slen; si++) {
            char sc = source.charAt(si);
            char scupper = Character.toUpperCase(sc);

            if (ti < tlen && scupper == target.charAt(ti)) {
                ti++;
            } else if (sc == scupper) {
                return false;
            }
        }

        return ti == tlen;
    }

    @Test
    public void test() {
        assertThat(canBeConverted("Pi", "P")).isEqualTo(true);
        assertThat(canBeConverted("AfPZN", "APZNC")).isEqualTo(false);
        assertThat(canBeConverted("LDJAN", "LJJM")).isEqualTo(false);
        assertThat(canBeConverted("UMKFW", "UMKFW")).isEqualTo(true);
        assertThat(canBeConverted("KXzQ", "K")).isEqualTo(false);
        assertThat(canBeConverted("LIT", "LIT")).isEqualTo(true);
        assertThat(canBeConverted("QYCH", "QYCH")).isEqualTo(true);
        assertThat(canBeConverted("DFIQG", "DFIQG")).isEqualTo(true);
        assertThat(canBeConverted("sYOCa", "YOCN")).isEqualTo(false);
        assertThat(canBeConverted("JHMWY", "HUVPW")).isEqualTo(false);
    }
}

The idea is to start at the beginning of the mixed-case string and to check off each matching character from the target string as it matches. If, after having gone through the whole source string, you checked off each of the target characters in the correct order, you're done and successful.

Compared to your algorithm, this one is much faster and consumes no extra memory. It runs in \$\mathcal O(slen)\$ time and \$\mathcal O(1)\$ space, where \$slen\$ is the length of the source string.

Your algorithm runs in \$\mathcal O(slen\times tlen)\$ time and needs \$\mathcal O(slen\times tlen)\$ space.