PROBLEM LINK:
Author: Shreyas Barve
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
You will be given a string s.
You have to find the longest palindrome which can be formed by elimination of consecutive letters from between. i.e. you need to delete characters from index i to j where j ≥ i, i≥ 1, j ≤ n (1 based indexing).
Print the longest palindrome possible after deleting a contiguous subsequence of length ≥ 0 from between.
Rules:
- You cannot add any new characters.
- You can not change order of the original string.
- Absolute difference of number of characters chosen from beginning and number of characters chosen from end of the string in the palindrome should be ≤1≤1.
Note: If more than one answer is possible, print lexicographically smallest one.
QUICK EXPLANATION:
We keep two pointers - i = 1 and j = n. We are checking the first and last character of the string and if they are equal we are incrementing the counter from left by one and decrementing the counter from right by one.
This is similar to trimming the extreme characters if they are equal.
If the counter from the left overtakes the counter from the right. i.e. they are adjacent to each other. This means that the string itself is palindrome.
The else condition is when we are no more getting similar characters from both ends and the counters have not reached next to each other.
s[ : i] represents the string till the counter i has travelled.
s[j+1:] represents the string till which counter j has travelled. This string will be palindrome of the string s[:i].
The middle part i.e. min(s[i],s[j]) gets the characters which are next to the strings which are included in the counter.
Now since the string is a palindrome, it will be of an even length. So we will take lexicographically smaller character between the two (1: which is in front of string s[:i] and 2: which is before the string s[j+1:])
Finally we print the answer.
SOLUTION:
Setter's Solution
def get_palindrome(s):
length = 0
n = len(s)
i = 0
j = n - 1
while i < j:
if (s[i] != s[j]):
break
i += 1
j -= 1
length += 1
ans = s[0 : length]
remaining = s[length : length + (n - (2 * length))]
x = s[length]
y = remaining[-1]
if (x < y):
ans += x
else:
ans += y
ans += s[n - length : n]
return ans
t = int(input())
for i in range(t):
s = input().strip()
ans = get_palindrome(s)
print (ans)