### 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.