GoodString
SRM 666 · 2015-06-30 · by praveen123
Problem Statement
Chandan loves to play with strings. He just learned a new operation: inserting one string X into another string Y.
When inserting X into Y, it is also allowed to place X at the beginning or at the end of Y. For example, there are exactly five ways how to insert the string "ab" into the string "????": you can produce one of the strings "ab????", "?ab???", "??ab??", "???ab?", and "????ab".
According to Chandan, a good string is a string that can be constructed in the following way: Initially, he takes the empty string "". Then, he performs a sequence of zero or more steps. In each step he inserts the string "ab" anywhere into the current string.
According to the above definition, the strings "ab", "aabb", and "aababb" are good while the strings "aab", "ba", and "abbb" are not good.
Chandan's friend Ravi came up with a
Constraints
- s will contain between 1 and 50 characters, inclusive.
- Each element of s will be either 'a' or 'b'.
"ab" Returns: "Good"
Chandan can start with an empty string and insert "ab".
"aab" Returns: "Bad"
"aabb" Returns: "Good"
Chandan can construct this string as follows: "" -> "ab" -> "aabb".
"ababab" Returns: "Good"
One way to construct this string is to append "ab" to the current string three times.
"abaababababbaabbaaaabaababaabbabaaabbbbbbbb" Returns: "Bad"
Submissions are judged against all 85 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GoodString with a public method string isGood(string s) · 85 test cases · 2 s / 256 MB per case