Connection Status:
Competition Arena > ManageSubsequences

ManageSubsequences

SRM 727 · 2018-01-10 · by Errichto

SRM 727 · 2018-01-10 · by Errichto · Dynamic Programming, String Manipulation
Class Name: ManageSubsequences
Return Type: int
Method Name: minAdded
Arg Types: (string, string, string)
Problem Statement

Problem Statement

Definition: for two strings X and Y, we say that a string X has a subsequence Y if and only if it's possible to remove 0 or more characters in X so that the remaining characters form the string Y. For example, "ABCDEFFF" has subsequences "B", "ABFF" and "ABCDEFFF", but doesn't have subsequences "XSFJ", "BA" and "CCDD".


Limak has a string S that consists of uppercase English letters ('A' - 'Z'). He can add more characters (also uppercase English letters) in S. For example, if S is "ABXB", he can get "BAOUBXBB" by inserting 'B', 'O', 'U' and 'B'.


You are given three Strings S, A and B, each consisting of uppercase English letters. Limak wants to add characters anywhere into S, including its beginning and end, so that the new string has the subsequence A but doesn't have the subsequence B. Find and return the minimum possible number of added characters. If Limak can't obtain a string with the desired properties, return -1 instead.

Constraints

  • S will contain between 1 and 300 characters, inclusive.
  • A will contain between 1 and 300 characters, inclusive.
  • B will contain between 1 and 300 characters, inclusive.
  • Each character in S, A and B will be an uppercase English letter ('A' - 'Z').
Examples
0)
"ABXBCA"
"ABCD"
"XD"
Returns: 2

Limak has the string "ABXBCA". Adding 'D' at the end would be enough to obtain a string that has the subsequence "ABCD" as needed, but the new string can't have the subsequence "XD". Limak should add 'C' and 'D' just after the first 'B' in the "ABXBCA", obtaining "ABCDXBCA". The number of added characters is 2.

1)
"BXC"
"BOCZ"
"DSFHDS"
Returns: 2

Limak has the string "BXC" and wants to obtain a string that has the subsequence "BOCZ" and doesn't have the subsequence "DSFHDS". For example, he can add 'O' just after 'B', and add 'Z' at the end, getting the string "BOXCZ". The number of added characters is 2.

2)
"BXC"
"BOCZ"
"BZ"
Returns: -1

The new string must have the subsequence "BOCZ" but can't have the subsequence "BZ", what is impossible. You should return -1.

3)
"ABC"
"CDE"
"ABCE"
Returns: 3
4)
"BANANA"
"APPLE"
"ANNA"
Returns: -1

Submissions are judged against all 166 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ManageSubsequences with a public method int minAdded(string S, string A, string B) · 166 test cases · 2 s / 256 MB per case

Submitting as anonymous