Chef Palin, as his name suggests, is always very interested in palindromic strings. Recently, he made a pretty interesting discovery on palindromes and that made him feel really Lucky. He came across something known as Lucky Palindromes. He defines a string as being a lucky palindrome if it is a palindrome containing the string "lucky" as a substring. As always, now he wants to turn every string he comes across into a lucky palindrome. Being a chef, he is a man of patience and creativity, so he knows the operation of replacing any character of the string with any other character very well and he can perform this action infinitely many times. He wants you to write a program that can help him convert a given string to a lucky palindrome using the minimum number of operations and if several such lucky palindromes are possible, then output the lexicographically smallest one.

------ Input Format ------ 

The first line contains a single integer T ≤ 100 the number of testcases. The following T lines each contain a string of length ≤ 1000 and only containing characters 'a'-'z'.

------ Output Format ------ 

For each line of testcase, your program should output on a single line, the required lucky palindrome along with the minimum number of operations, both separated by a single space. If there is no lucky palindrome possible, then just output "unlucky" in a single line.

----- Sample Input 1 ------ 
3
laubcdkey
luckycodechef
aaaaaaaa
----- Sample Output 1 ------ 
luckykcul 8
luckycocykcul 6
unlucky

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Ad-hoc

Greedy algorithms


Solutions:
def inBounds(index, l, r):
	if index >= l and index <= r:
		return True
	return False
for _ in range(int(input())):
	s = input().strip()
	l = len(s)
	if l < 9:
		print('unlucky')
		continue
	count = 0
	minimum = 10000000000
	answer = ''
	for index in range(l - 5 + 1):
		copyStr = list(s)
		count = 0
		if copyStr[index] != 'l':
			copyStr[index] = 'l'
			count += 1
		if copyStr[index + 1] != 'u':
			copyStr[index + 1] = 'u'
			count += 1
		if copyStr[index + 2] != 'c':
			copyStr[index + 2] = 'c'
			count += 1
		if copyStr[index + 3] != 'k':
			copyStr[index + 3] = 'k'
			count += 1
		if copyStr[index + 4] != 'y':
			copyStr[index + 4] = 'y'
			count += 1
		i = 0
		j = len(copyStr) - 1
		l = index
		r = index + 4
		found = True
		while i <= j:
			if copyStr[i] != copyStr[j]:
				if (i < l or i > r) and (j < l or j > r):
					if copyStr[i] < copyStr[j]:
						copyStr[j] = copyStr[i]
						count += 1
					else:
						copyStr[i] = copyStr[j]
						count += 1
				elif inBounds(i, l, r):
					if j < l or j > r:
						copyStr[j] = copyStr[i]
						count += 1
					else:
						found = False
						break
				elif inBounds(j, l, r):
					if i < l or i > r:
						copyStr[i] = copyStr[j]
						count += 1
					else:
						found = False
						break
				else:
					found = False
					break
			i += 1
			j -= 1
		if found:
			if count < minimum:
				minimum = count
				answer = ''.join(copyStr)
			elif minimum == count:
				string = ''.join(copyStr)
				answer = min(answer, string)
	if minimum == 10000000000:
		print('unlucky')
	else:
		print(answer, minimum)


def inbOunds(index, l, r):
	if index >= l and index <= r:
		return True
	return False
t = int(input())
for _ in range(t):
	s = input().strip()
	l = len(s)
	count = 0
	mini = 10000000000
	ans = ''
	for index in range(l - 5 + 1):
		copyStr = list(s)
		count = 0
		if copyStr[index] != 'l':
			copyStr[index] = 'l'
			count += 1
		if copyStr[index + 1] != 'u':
			copyStr[index + 1] = 'u'
			count += 1
		if copyStr[index + 2] != 'c':
			copyStr[index + 2] = 'c'
			count += 1
		if copyStr[index + 3] != 'k':
			copyStr[index + 3] = 'k'
			count += 1
		if copyStr[index + 4] != 'y':
			copyStr[index + 4] = 'y'
			count += 1
		i = 0
		j = len(copyStr) - 1
		l = index
		r = index + 4
		found = True
		while i <= j:
			if copyStr[i] != copyStr[j]:
				if (i < l or i > r) and (j < l or j > r):
					if copyStr[i] < copyStr[j]:
						copyStr[j] = copyStr[i]
						count += 1
					else:
						copyStr[i] = copyStr[j]
						count += 1
				elif inbOunds(i, l, r):
					if j < l or j > r:
						copyStr[j] = copyStr[i]
						count += 1
					else:
						found = False
						break
				elif inbOunds(j, l, r):
					if i < l or i > r:
						copyStr[i] = copyStr[j]
						count += 1
					else:
						found = False
						break
				else:
					found = False
					break
			i += 1
			j -= 1
		if found:
			if count < mini:
				mini = count
				ans = ''.join(copyStr)
			elif mini == count:
				string = ''.join(copyStr)
				ans = min(ans, string)
	if mini == 10000000000:
		print('unlucky')
	else:
		print(ans, mini)