FindStringHard
TCO19 SRM 746 · 2019-01-09 · by majk
Problem Statement
An antipalindrome is a string which differs from its own reverse at all positions. For instance, "ab", "aabb", "abab", and "abbaab" are antipalindromes, whereas "aaab", "abba", "aababa", "baa", and "a" are not.
A substring is a nonempty contiguous part of a given string. For instance, "aba" is a substring of "aaba" but "aaa" isn't.
Two substrings are considered different if they are located at different positions in the string. For instance, there are two distinct substrings "aba" in the string "ababa".
You are given an
- Its length is at most 100.
- Each character is either 'a' or 'b'.
- The string has exactly n antipalindromic substrings.
Notes
- It can be shown that the answer always exists. If there are multiple solutions, you may print any of them.
- It is not necessary to minimize the length of the returned string.
Constraints
- The integer n will be between 0 and 1000, inclusive.
3 Returns: "bbaab"
The three antipalindromic substrings of "bbaab" are "bbaa", "ba", and "ab".
8 Returns: "ababbaab"
The eight antipalindromic substrings of "ababbaab" are three copies of "ab", two copies of "ba", and one copy each of "abab", "bbaa", and "abbaab".
139 Returns: "ababaabbaabbaaabbbaaabbbaaaabbbbaaaabbbbaaaaabbbbbaaaaabbbbbaaaaaabbbbbbaaaaaabbbbbb"
0 Returns: "a"
1 Returns: "abbb"
Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FindStringHard with a public method string withAntipalindromicSubstrings(int n) · 87 test cases · 2 s / 256 MB per case