MarriageAndSelectionChallenge
SRM 803 · 2021-03-30 · by misof
Problem Statement
One of the challenges after marriage is to select which friends to invite to your house.
When inviting friends, their political party is important. There are 12 political parties in Iran. We will label them 'a', 'b', ..., 'l'.
You are given a
The friends you invite will sit at a table in the order in which they were in the original sequence. When choosing whom to invite, we want to make sure that there are no three friends i < j < k that were all invited such that S[i] = S[k] and S[i] != S[j].
We want to maximize the number of friends invited to our house. If there are multiple optimal solutions, for each of them we will write down the parties of the invited friends as a string, and we will pick an optimal solution for which that string is the lexicographically smallest. Find and return that string.
Constraints
- S will contain between 1 and 3,000 characters, inclusive.
- Each character in S will be one of the first 12 English letters ('a'-'l').
"kick" Returns: "ick"
We cannot invite all four friends, because S[0] = S[3] and S[0] != S[1]. There are two ways in which we can invite three friends: either we invite friends 0,1,2 or friends 1,2,3. In the first case we get the string "kic", in the second case the string "ick". As "kic" > "ick", our answer is "ick".
"cccaaccc" Returns: "cccccc"
The optimal solution is to invite everyone from party 'c'.
"abcdeedcba" Returns: "abcdee"
"ecabddbace" Returns: "abddce"
"ccaaccc" Returns: "aaccc"
Now the optimal solution is to invite friends 2-6. Inviting everyone from party 'c' gives the same total number of friends but a lexicographically larger string.
Submissions are judged against all 39 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MarriageAndSelectionChallenge with a public method string solve(string S) · 39 test cases · 2 s / 256 MB per case