A page in an address book contains two addresses. Each address is written as a string of lowercase letters and digits.

Find the length of the longest sequence of characters shared by both addresses. This sequence contains matching characters that appear in the same order in both addresses. You may skip characters, but you cannot rearrange the characters you keep. The kept characters do not need to be next to one another.

Class

AddressSimilarityAnalyzer

Constructor

AddressSimilarityAnalyzer

AddressSimilarityAnalyzer()

• Creates a new address similarity analyzer.

Method

findLongestSharedSequence

public int findLongestSharedSequence(String firstAddress, String secondAddress)

• firstAddress is the first address.
• secondAddress is the second address.
• Returns the greatest possible number of matching characters that can be kept in the same order in both addresses.

Rules

• You may skip zero or more characters from either address.
• You must not change the order of the characters you keep.
• The kept characters do not need to be next to one another.
• The kept characters must match exactly in both addresses.
• Every letter and digit is compared exactly.
• If the addresses share no characters, return 0.
• The input strings must not be modified.

Constraints

• 1 ≤ firstAddress.length(), secondAddress.length() ≤ 1,000
• firstAddress and secondAddress contain only lowercase English letters and digits.
• firstAddress and secondAddress are non-null.

Expected Efficiency

• Let m = firstAddress.length() and n = secondAddress.length().
• The method should run in O(mn) time.
• The method should use O(mn) additional space or less.

Deterministic Output

The method returns only the greatest possible length. If several matching sequences have this length, the returned integer is still the same.

Examples

Example 1

findLongestSharedSequence( firstAddress = "12parkstreet", secondAddress = "12street")

Output: 8

All eight characters of "12street" appear in the same order in both addresses.

Example 2

findLongestSharedSequence( firstAddress = "45northroad", secondAddress = "45southroad")

Output: 9

The nine characters in "45othroad" can be kept in the same order in both addresses.

Example 3

findLongestSharedSequence( firstAddress = "pine", secondAddress = "42road")

Output: 0

The two addresses have no character in common.