AnagramSplitting
SRM 476 · 2009-12-03 · by gojira_tc
SRM 476 · 2009-12-03 · by gojira_tc · Dynamic Programming
Problem Statement
Problem Statement
A string X is an anagram of string Y if X can be obtained by arranging all characters of Y in some order, without removing any characters and without adding new characters. For example, each of the strings "baba", "abab", "aabb" and "abba" is an anagram of "aabb", and strings "aaab", "aab" and "aabc" are not anagrams of "aabb".
A string X is a subsequence of string Y if X can be obtained by removing some characters (possibly none) from Y and preserving the order of the remaining characters. For example, each of the strings "ac", "abd", "abcd" is a subsequence of "abcd", and strings "ca", "abb" and "abcde" are not subsequences of "abcd".
A string X is called a subanagram of Y if there exists a string Z such that X is an anagram of Z and Z is a subsequence of Y.
Manao is a big fan of subanagrams and he tries to find them everywhere. This time, he works on splitting strings into several parts in such a way that each of the parts (except the last one) is a subanagram of the following part. Formally, for a given string X, Manao wants to split it into several non-empty strings S1, S2, ..., Sn such that their concatenation S1 + S2 + ... + Sn equals X and each string Si (0 < i < n) is a subanagram of string Si+1.
You're given aString[] suppliedWord. Concatenate all its elements in the order they are given to obtain a single string X. Return the maximum number of parts into which Manao can split X so that the condition from the previous paragraph is satisfied.
A string X is a subsequence of string Y if X can be obtained by removing some characters (possibly none) from Y and preserving the order of the remaining characters. For example, each of the strings "ac", "abd", "abcd" is a subsequence of "abcd", and strings "ca", "abb" and "abcde" are not subsequences of "abcd".
A string X is called a subanagram of Y if there exists a string Z such that X is an anagram of Z and Z is a subsequence of Y.
Manao is a big fan of subanagrams and he tries to find them everywhere. This time, he works on splitting strings into several parts in such a way that each of the parts (except the last one) is a subanagram of the following part. Formally, for a given string X, Manao wants to split it into several non-empty strings S1, S2, ..., Sn such that their concatenation S1 + S2 + ... + Sn equals X and each string Si (0 < i < n) is a subanagram of string Si+1.
You're given a
Constraints
- suppliedWord will contain between 1 and 10 elements, inclusive.
- Each element of suppliedWord will contain between 1 and 50 characters, inclusive.
- suppliedWord will consist of uppercase letters ('A'-'Z') only.
Examples
0)
{"ABABAB"}
Returns: 3
Manao can split the given string in three "AB"-s.
1)
{"AAXAAAABX"}
Returns: 4
One of the possible ways to split "AAXAAAABX" into 4 parts is "A"+"A"+"XA"+"AAABX". "XA" is the anagram of "AX", a subsequence of "AAABX".
2)
{"ABCDEFGHIJKL"}
Returns: 1
This word is not splittable.
3)
{"ABBAB","B","BBX","Z"}
Returns: 2
Don't forget to concatenate the given strings.
4)
{"EEEEEOSVLISKXEUPYWZA"}
Returns: 6
Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SubAnagrams with a public method int maximumParts(vector<string> suppliedWord) · 68 test cases · 2 s / 256 MB per case