Common Child

A string is said to be a child of a another string if it can be formed by deleting 0 or more characters from the other string. Given two strings of equal length, what's the longest string that can be constructed such that it is a child of both?

For example, ABCD and ABDC have two children with maximum length 3, ABC and ABD. They can be formed by eliminating either the D or C from both strings. Note that we will not consider ABCD as a common child because we can't rearrange characters and ABCD  ABDC.

Function Description

Complete the commonChild function in the editor below. It should return the longest string which is a common child of the input strings.

commonChild has the following parameter(s):

• s1, s2: two equal length strings

Input Format

There is one line with two space-separated strings,  and .

Constraints

• All characters are upper case in the range ascii[A-Z].

Output Format

Print the length of the longest string , such that  is a child of both  and .

Sample Input

HARRY
SALLY

Sample Output

 2

Explanation

The longest string that can be formed by deleting zero or more characters from  and  is , whose length is 2.

Sample Input 1

AA
BB

Sample Output 1

0

Explanation 1

 and  have no characters in common and hence the output is 0.

Sample Input 2

SHINCHAN
NOHARAAA

Sample Output 2

3

Explanation 2

The longest string that can be formed between  and  while maintaining the order is .

Sample Input 3

ABCDEF
FBDAMN

Sample Output 3

2

Explanation 3 
 is the longest child of the given strings.

---

이 문제를 이해하기 위해서는 같은 길이의 문자열을 Matrix 구조로 보고 계산을 해야 한다.

자세한 설명은 다음 URL을 참고해야 한다. 복잡한 수식으로 설명되어 있지만, 대략적으로 어떤 구조로 이해해야 하는지 알 수 있다.

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

역시 Medium 레벨이고, 혼자 풀다가 풀다가 결론을 맺지 못하여 Discussion의 내용을 참고하였다.