PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
The problem is solvable by Greedy Algorithm. For each i >= 0 and j >=0, i < j such that string[i….j] = “lucky”, find the lexicographically smallest palindrome that can be constructed in a greedy manner using minimum number of replacement operations. So the problem can be divided into two tasks:
- Place the substring “lucky” at all possible locations in the string.
- For each such location of substring “lucky”, find the lexicographically smallest palindrome using minimum number of replacement operations while maintaining the substring “lucky”.
Let’s define each string obtained in task 1 as: “xxxxxluckyxxxxx” with str[a…b] = “lucky”. Now, second task can be achieved by iterating over the string starting with i = 0 and j = n-1 (n = string length), until i <= j. At each iteration, we have the following possibilities:
- str[i] = str[j] , requires no replacement operation
- str[i] != str[j] , either requires 1 replacement or no solution is possible
a. i < a and j > b, requires 1 replacement
i. if str[i] < str[j], str[j] = str[i]
ii. str[i] > str[j], str[i] = str[j]
b. a >= i and i <= b and j > b, requires 1 replacement
i. str[j] = str[i], cannot change str[i] as it is part of “lucky”
c. i < a and a >= j and j <= b, requires 1 replacement
i. str[i] = str[j], cannot change str[j] as it is part of “lucky”
d. a >= i,j <= b, cannot be converted to palindrome containing “lucky”
Final answer is the string obtained after task 2 with minimum number of replacement operations and lexicographically smallest one. If no such string exists, then “unlucky”.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.