MaxDistinctPairs
SRM 838 · 2022-09-19 · by misof
Problem Statement
You are given the
You are only allowed to use the first N uppercase English letters. For example, if N = 3 you may only use 'A', 'B', and 'C'; while N = 26 means that you may use the whole alphabet.
The string partial contains some periods ('.') and some letters. All letters used in partial also belong among the first N uppercase English letters - no other letters will appear in this string.
Your have to replace each period by one of the N allowed letters. Your task is to maximize the number of pairs of consecutive letters in which the two letters differ.
Replace all periods with allowed letters and then return the resulting string. If there are multiple optimal solutions, you may return any one of them.
Constraints
- N will be between 1 and 26, inclusive.
- partial will have between 0 and 2,500 characters, inclusive.
- Each character in partial will be either '.' or one of the first N uppercase English letters.
26 "........" Returns: "ABABABAB"
We can replace each period with any of the 26 uppercase English letters. As the result is a string of length 8, it has 7 pairs of consecutive letters. We can easily make all seven pairs count.
1 "..A.A..A" Returns: "AAAAAAAA"
The only letter we are allowed to use is 'A'. There is exactly one string we can create. It contains no good pairs of consecutive letters, but as it's the only valid string, it's still the best solution.
6 "A....FA....F" Returns: "ABCDEFABCDEF"
Again, there are no pairs of consecutive equal letters.
2 "B.A" Returns: "BAA"
We can only choose between 'A' and 'B' for this '.'. Regardless of what we choose, exactly one of the two pairs of consecutive letters will be good.
1 "" Returns: ""
7 "" Returns: ""
An empty partial string. There are no letters to fill in, so the answer is also an empty string. The empty string contains zero pairs of consecutive letters.
Submissions are judged against all 125 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MaxDistinctPairs with a public method string maximize(int N, string partial) · 125 test cases · 2 s / 256 MB per case