2

The Problem definition:

Given two strings a and b of equal length, what’s the longest string (S) that can be constructed such that S is a child to both a and b. String x is said to be a child of string y if x can be formed by deleting 0 or more characters from y

Input format

Two strings a and b with a newline separating them

Constraints

All characters are upper-cased and lie between ascii values 65-90 The maximum length of the strings is 5000

Output format

Length of the string S

Sample Input #0

HARRY SALLY

Sample Output #0

2

The longest possible subset of characters that is possible by deleting zero or more characters from HARRY and SALLY is AY, whose length is 2.

The solution:

public class Solution {
  public static void main(String[] args) throws Exception {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    char[] a = in.readLine().toCharArray();
    char[] b = in.readLine().toCharArray();
    int[][] dp = new int[a.length + 1][b.length + 1];
    dp[0][0] = 1;
    for (int i = 0; i < a.length; i++)
        for (int j = 0; j < b.length; j++)
           if (a[i] == b[j])
              dp[i + 1][j + 1] = dp[i][j] + 1;
           else
              dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
              System.out.println(dp[a.length][b.length]);
  }
}

Anyone has encountered this problem and solved using the solution like this? I solved it in a different way. Only found this solution is elegant, But can not make sense of it so far. Could anyone help explaining it little bit.

2

1 Answer 1

2

This algorithm uses Dynamic Programming. The key point in understanding dynamic programming is to understand the recursive step which in this case is within the if-else statement. My understanding about the matrix of size (a.length+1) * (b.length +1) is that for a given element in the matrix dp[i +1, j +1] it represents that if the we only compare string a[0:i] and b[0:j] what will be the child of both a[0:i] and b[0:j] that has most characters.

So to understand the recursive step, let's look at the example of "HARRY" and "SALLY", say if I am on the step of calculating dp[5][5], in this case, I will be looking at the last character 'Y':

A. if a[4] and b[4] are equal, in this case "Y" = "Y", then i know the optimal solution is: 1) Find out what is the child of "HARR" and "SALL" that has most characters (let's say n characters) and then 2) add 1 to n.

B. if a[4] and b[4] are not equal, then the optimal solution is either Child of "HARR" and "SALLY" or Child of "HARRY" and "SALL" which will translate to Max(dp[i+1][j] and dp[i][j+1]) in the code.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.