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

• Mast: What part of your solution is recursive and why isn't it contained in it's own function?
• kumarmo2: Actually i have skipped the recursion part and i have went ahead and used memoization(dp). If it makes anything clearer i can add the recursive solution as well to the question.
• Mast: No, if this is your final solution, this will do. It's just that the tags are misleading now. I'll fix them for you.
• Rob Audenaerde: Some comments and refactor might be nice, the block of code with many indent levels is not easy to understand right now.

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.

• kumarmo2: @mdfsr13 Didnt think i would receive such a detailed answer. I actually learned few new things and some major best practices. Thanks.

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.

• kumarmo2: Can you confirm if your code passes for a="BBbcA" and b="BCA".. Output should be NO
• Roland Illig: Confirmed. (By running the code in my head instead of on an actual computer.) I would have tried my code on HackerRank, but they require a sign-in.
• kumarmo2: I have editted the question to include the sample case your algo is failing. If you want you can take a look. thanks.
• Roland Illig: The updated version of my code runs all tests correctly while keeping the original idea and the performance.
• kumarmo2: your test case is failing for this input. a = "BBb", b = "B". Problem with your approach is you are not taking into consideration that small letters might even not be needed for the answer. Once you are seeing that capitalizing the the lower case alphabet matches the alphabet in string b, you are incrementing ti. you need to consider a case when it might not be needed according to the problem.