PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY
PREREQUISITES:
Greedy
PROBLEM:
You’re given a string S. You can perform at most k moves. Each move consists of shifting one of the letters by 1. Determine the lexicographically smallest palindrome you can achieve.
QUICK EXPLANATION:
This problem is not difficult, but there might be some tricky cases which you have to avoid. The solution is explained in the section below.
EXPLANATION:
For subtask 1, iterating through all possible string suffices. The complexity for this is O(26^{|s|} \cdot |s|).
We’ll directly solve subtask 3. Now, to produce a lexicographical string we want the first letter to be as small as possible, then the second letter should be as small as possible, and so on… However, the problem requires the resulting string to be a palindrome as well, so more work needs to be done.
First, we have to turn S into a palindrome. Let f(i, j) denote the minimum number of seconds needed to turn the i-th character and the (n - 1 - i)-th character (n is the length of s, the characters are 0-indexed) into letter j. This value is easy to calculate for all i and j in O(1). Now, we first convert S into a palindrome using the minimum number of seconds, by choosing the letter j with the minimum value of f(i, j) for each i. (and breaking ties by choosing the j that appears first in the alphabet)
Suppose at this point we still have x seconds left. If x < 0, there’s no solution. Otherwise, we can improve our solution. We start improving the string from the first letter. We try to make the first letter as small as possible, provided we can perform at most x moves. We keep improving the string until x = 0. This greedy solution works because to get the lexicographically smallest string we must minimize the first letter, then the second letter and so on. This solution works in O(|s| \cdot 26) time.
There are a few tricky cases for this problem :
- 3 yz
- 2 x
- 1 a
- 8 fx
- 4 xa
The answers to these cases are :
- a
- v
- a
- aa
- aa
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.