RemoveCharacters
2016 TCO Algo 3B · 2016-03-24 · by cgy4ever
Problem Statement
This proposal was rejected with the comment that it is too classic. Apparently, everybody knows that it can be solved by using dynamic programming to compute the longest common subsequence of the two strings.
Ciel then suggested to make the task less classic by adding a single word: changing "smallest number of characters" into "smallest number of distinct characters". More precisely, you are still allowed to remove any subset of characters, but this time we want you to minimize the number of distinct characters among the characters you remove.
Solve this new version of Ciel's task.
Constraints
- A will contain between 1 and 1,000 elements, inclusive.
- B will contain between 1 and 1,000 elements, inclusive.
- Each character in A will be a lowercase English letter (i.e. 'a'-'z').
- Each character in B will be a lowercase English letter (i.e. 'a'-'z').
"acabc" "accabcc" Returns: 1
One optimal solution here is to remove characters at 0-based indices 1 and 6 in the string B. Both removed characters are 'c's. This changes the string B from "accabcc" to "acabc" and makes the two strings equal. As we only removed one distinct character, the correct return value is 1.
"aabbcc" "ccbbaa" Returns: 2
One optimal solution is to remove the first four characters of A and the last four characters of B. After this change, both strings become equal to "cc". We removed two distinct characters: some 'a's and some 'b's.
"aaaabc" "bcaaaaa" Returns: 1
The optimal solution here is to remove all nine 'a's. Note that we are only interested in minimizing the number of distinct characters among the characters we remove. The total number of removed characters may be arbitrary.
"abcde" "abcde" Returns: 0
"abcdefghijklm" "nopqrstuvwxyz" Returns: 26
We need to remove all of them.
Submissions are judged against all 125 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RemoveCharacters with a public method int minimalDistinct(string A, string B) · 125 test cases · 2 s / 256 MB per case