Question :- Find the longest palindrome

As we all know, a palindrome is a word that equals its reverse. Here are some examples of palindromes: malayalam, gag, appa, amma.

We consider any sequence consisting of the letters of the English alphabet to be a word. So axxb,abbba and bbbccddx are words for our purpose. And aaabbaaa, abbba and bbb are examples of palindromes.

By a subword of a word, we mean a contiguous subsequence of the word. For example the subwords of the word abbba are ababbbbaabbbbbbbaabbbbbba and abbba.

In this task you will given a word and you must find the longest subword of this word that is also a palindrome.

For example if the given word is abbba then the answer is abbba. If the given word is abcbcabbacba then the answer is bcabbacb.

Solution hint

Any subword of w that is a palindrome is also a subword when w is reversed.

Input format

The first line of the input contains a single integer N indicating the length of the word. The following line contains a single word of length N, made up of the letters a,b,…, z.

Output format

The first line of the output must contain a single integer indicating the length of the longest subword of the given word that is a palindrome. The second line must contain a subword that is a palindrome and which of maximum length. If there is more than one subword palindrome of maximum length, print the one that is lexicographically smallest (i.e., smallest in dictionary order).

Test Data:

You may assume that 1 ≤ N ≤ 5000. You may further assume that in 30% of the inputs 1 ≤ N ≤ 300.

Example:

We illustrate the input and output format using the above examples:

Sample Input 1:

5
abbba

Sample Output 1:

5
abbba

Sample Input 2:

12
abcbcabbacba

Sample Output 2:

8
bcabbacb

Solution (90.0/100.0) :- #Please comment if you find any changes for 100.0/100.0

n = int(input())

s = input()
s_r = s[::-1]

o_n = 0
o_s = ""

for i in range(n+1):
    for j in range(i+1, n+1):
        palin = s[i:j]
        if s_r.find(palin)!=-1:
            if (o_n < len(palin)) or (o_n == len(palin) and o_s < palin):
                o_n = len(palin)
                o_s = palin

print(o_n)
print(o_s)

 

 
Categories: NPTEL solution

23 Comments

Saurabh · September 18, 2017 at 6:29 AM

by this solution, the score is only (80.00/100)

pavan · September 18, 2017 at 6:55 AM

thank you soo much sir

k.vijayalakshmi · September 18, 2017 at 11:28 AM

i got only 80 marks please update the answer

    Saurab.B · September 21, 2017 at 5:24 PM

    me too

ravichandra · September 18, 2017 at 10:12 PM

for input
4
asdfdsa

output is
4
asdf

but shouldnt it be none or something

similarly for inputs as
4
dssassa
output is
3
ssa

Anuj jain · September 19, 2017 at 2:40 AM

def longestPalSubstr(string):
maxLength = 1

start = 0
length = len(string)

low = 0
high = 0

# One by one consider every character as center point of
# even and length palindromes
for i in range(1, length):
# Find the longest even length palindrome with center
# points as i-1 and i.
low = i – 1
high = i
while low >= 0 and high maxLength:
start = low
maxLength = high – low + 1
low -= 1
high += 1

# Find the longest odd length palindrome with center
# point as i
low = i – 1
high = i + 1
while low >= 0 and high maxLength:
start = low
maxLength = high – low + 1
low -= 1
high += 1

print (maxLength)
print (string[start:start + maxLength])

n=int(input())
string=input()
longestPalSubstr(string)

Anuj jain · September 19, 2017 at 2:43 AM

100.0/100.0 marks

Anurag · September 19, 2017 at 5:12 AM

I too got only 80.

Prudhvi Raj Medikonduri · September 19, 2017 at 6:33 PM

def pal1(k):
for x in range(len(k)//2+1):
if k[x] != k[(len(k)-1)-x]:
return 1

return len(k)

def pal(s):
max=1
k=””
str=””
y=1
if len(s)==1:
return (1,s)
for i in range(0,len(s)):
k=s[i:i+max]

for j in range(i+max,len(s)):
k=k+s[j]
y=pal1(k)

if y>max:
max=y
str=k
elif y==max:
if str len(s)/2:
return (max,str)
return (max,str)

l=int(input())
s=input()
(max,str)=pal(s)
print(max)
print(str)

siva · September 20, 2017 at 3:24 PM

i got 60

Vishal · September 20, 2017 at 3:53 PM

I too got only 80 marks

apk · September 20, 2017 at 4:12 PM

i got only 60 marks
plz do something

saurab · September 21, 2017 at 4:58 AM

please check the code because we are not getting 100

Hiranmai · September 21, 2017 at 1:55 PM

Please update I got only 80 marks

lakith · September 21, 2017 at 1:57 PM

i scored only 60, please change the solution

    Prudhvi Raj Medikonduri · September 21, 2017 at 2:54 PM

    def pal1(k):
    for x in range(len(k)//2+1):
    if k[x] != k[(len(k)-1)-x]:
    return 1

    return len(k)

    def pal(s):
    max=1
    k=””
    str=””
    y=1
    if len(s)==1:
    return (1,s)
    for i in range(0,len(s)):
    k=s[i:i+max]

    for j in range(i+max,len(s)):
    k=k+s[j]
    y=pal1(k)

    if y>max:
    max=y
    str=k
    elif y==max:
    if str len(s)/2:
    return (max,str)
    return (max,str)

    l=int(input())
    s=input()
    (max,str)=pal(s)
    print(max)
    print(str)

Nims · September 21, 2017 at 4:08 PM

def longestPalSubstr(string):
maxLength = 1

start = 0
length = len(string)

low = 0
high = 0

# One by one consider every character as center point of
# even and length palindromes
for i in range(1, length):
# Find the longest even length palindrome with center
# points as i-1 and i.
low = i – 1
high = i
while low >= 0 and high maxLength:
start = low
maxLength = high – low + 1
low -= 1
high += 1

# Find the longest odd length palindrome with center
# point as i
low = i – 1
high = i + 1
while low >= 0 and high maxLength:
start = low
maxLength = high – low + 1
low -= 1
high += 1

print (maxLength)
print (string[start:start + maxLength])

n=int(input())
string=input()
longestPalSubstr(string)

kavin · September 21, 2017 at 4:15 PM

def longestPalSubstr(string,num):
maxLength = 1

start = 0
length = num

low = 0
high = 0
for i in range(1, length):
low = i – 1
high = i
while low >= 0 and high maxLength:
start = low
maxLength = high – low + 1
low =low-1
high =high+1
low = i – 1
high = i + 1
while low >= 0 and high maxLength:
start = low
maxLength = high – low + 1
low =low-1
high =high+1

print(maxLength)
print(string[start:start + maxLength])

num=int(input())
string=input()
longestPalSubstr(string,num)

pooja · September 21, 2017 at 4:37 PM

def longestPalSubstr(string,num):
maxLength = 1

start = 0
length = num

low = 0
high = 0
for i in range(1, length):
low = i – 1
high = i
while low >= 0 and high maxLength:
start = low
maxLength = high – low + 1
low =low-1
high =high+1
low = i – 1
high = i + 1
while low >= 0 and high maxLength:
start = low
maxLength = high – low + 1
low =low-1
high =high+1

print(maxLength)
print(string[start:start + maxLength])

num=int(input())
string=input()
longestPalSubstr(string,num)

    Yash Sodha · September 23, 2017 at 4:00 AM

    Thanks!

Aditya Nath Swami · September 21, 2017 at 6:17 PM

n = int(input())
text = input()
text = text.lower()
results = []
if not n == len(text):
print(‘Error’)
if len(text) == 1:
print(‘0’)
print(“”)
for i in range(n):
for j in range(i):
chunk = text[j:i+1]
if chunk == chunk[::-1]:
results.append(chunk)
print(len(max(results, key=len)))
results.sort()
print(max(results, key=len))
# You got 90 Marks. 😛

    Yash Sodha · September 23, 2017 at 4:00 AM

    Thank you 🙂

arasu su · September 22, 2017 at 12:11 PM

bro give sample test answers

Leave a Reply

Your email address will not be published. Required fields are marked *