11404 - Palindromic Subsequence

[ssangbuja]

I used DP solution to solve this problem, but I got TLE. It probably take O(n^3) to fill matrix.

[deleted]

any suggestion??

[Robert Gerbicz]

any suggestion??

There is a fast O(n^2) dp method (space requirement is also O(n^2) ) to determine the length of the longest palindrom, it's well known. But in this problem you have to print the lexicographically smallest palindrom, which is the longest, and you can do that in O(|size of alphabet|*n) time. (So the total time is O(n^2))

[ssangbuja]

So the total time is O(n^2)

Thanks Robert I got AC.

[w k]

I'm getting WA using DP method. Are there any special inputs for this problem?

Wojciech

[Robert Gerbicz]

I'm getting WA using DP method. Are there any special inputs for this problem?

Wojciech

There is no special case (but make sure that the word can be very long!).
But here some handgenerated small tests:

Code: Select all

h
hh
hy
yh
bab
abb
bba
abba
baba
abc
pu
bard
puma
abca
wyzw
wwww
book

The correct output is:

Code: Select all

h
hh
h
h
bab
bb
bb
abba
aba
a
p
a
a
aba
wyw
wwww
oo

And here it is computer generated (random) input:

Code: Select all

dj
inc
klje
f
tgsmb
camd
wuqrgoa
mnl
byjfwdy
fvzzgke
rqe
mvwkohogfsx
cuhpqfxiunxo
fnwfghlxlg
gwxbp
ptutmv
ixdzjgqulmofs
adooewvkzskhdshhb
ltr
vllszwcfmg
idqqbqjertwskxan
n
sthucm
oduartneikjrdwokcenazl
miymgoxfaikovni
olfjkahkhwepcoyrhsaeed
ykbpchdphhvtqjjqijzmfpbinxhr
mwpvynkyxvwz
httxnbkqg
yyusciwqurzxwqopscyfaorv
oturynskpb
pkgoxdyddjau
itylavuwslcgjqccaglzfifhiynudssgb
fjpnhawxcftjnrrrflpwfou
evxmcftyfvhpahl
zpdpurzruypsihwqk
qdqkvyeybyrjx
bokenrlnlrcsgbczi
fnajtziuuiasselcov
gmpiqbsrkwsffrlytak
knprzizjinmhaoesymmhzregsxudbanvwd
ksefaihytncrtqhwvhytpzxhh
grriqcxmtepetanjpiqvlsyyermepwcwdeluxzwx
fjyxnicmnppxwkntjdhyh
ndkkjzbaouql
siuhfovapcwpedsmxknkspsdueazeucocf
oguodmhctxglulbneieqdgdotczmpabtmbn
bngsoicogmbajkkinjukmzovvkrqpbcgwrulpzzfaafrolqz
bygsgvjjhwamsv
qxtalhgqdykgivewohltbkdfinmrtma
lczdrsfargkjgb
clzcqcxvrtdifzvbkjhhm
qeptxcuyppyydtpkefxsbhkteggmkmtqpnnjvgfxxcpesgjns
bhfczpzyawklrnaoarzshujggfpjqaxi
pqrodtkwpfyycjphtijvdnjc
vzcofter
vxywaztuw
zbynpvykntuibgwmq
dnpvirovb
kczjrozzjkjvonvfzyxlxdxpmpcqqbxarcexvjau
bksuivw
tys

See Rio's post to get the correct output for this input set!

[w k]

OK. I got it.

Wojciech

[srrajesh]

But in this problem you have to print the lexicographically smallest palindrom, which is the longest, and you can do that in O(|size of alphabet|*n) time. (So the total time is O(n^2))

Can you explain how you print lexicographically least palindrome with O(|size of alphabet|*n) time? I thought hard, i am not able to get how to do it! Do you use any other array, other than the one used to compute the length of the longest palindrome?

Thanks in advance.

[emotional blind]

To show the longest palindromic subsequence from index i to j, find first 'a' and last 'a' between i and j and calculate the length of longest subsequence of s[i+1] to s[j-1], do same thing with 'b' to 'z'. take the character for which it gives the largest subsequence, if two character gives the same result smaller one should be considered. and this character will be the first and last character of longest palindromic subsequence in between s and s[j]. Let the character first exists in index x and last exists in y, then do the same thing in s[x+1] to x[y-1].

[Anindya]

I am getting RTE,can any one help?

Robert,how for the input:

Code: Select all

pqrodtkwpfyycjphtijvdnjc

u get:

Code: Select all

dtpaaptd

PLZ expain.I can't see any 'a' in the input string.
Does ur AC code produces this output?

[rio]

My code outputs below for Robert's second input:

Code: Select all

d
c
e
f
b
a
a
l
ydy
zz
e
oho
ufu
glxlg
b
tut
d
dkskd
l
ll
qbq
n
c
anekdkena
ioaoi
ahcha
bpqjjqpb
wvykyvw
tt
ycqrqcy
b
ddd
ilacccali
fpfrrrfpf
vftfv
purzrup
qdq
brlnlrb
aiuuia
kffk
nrzhmmhzrn
hthvhth
xepeyyepex
jxncnxj
kk
foaedsknksdeaof
mctgeiegtcm
gcomjkkjmocg
sjjs
alhgdghla
gjg
zcqcz
epcptkebektpcpe
fzraoarzf
dtpyyptd
c
waw
bnknb
viv
jvxxpmpxxvj
b
s

This problem could also be solved by modified Hunt-Szymanski algorithm, an algorithm for LCS.
In this case, you could get the lexicographically smallest palindrome by calculating the lexicographically smallest LCS.
-----
Rio

[sohel]

This problem could also be solved by modified Hunt-Szymanski algorithm, an algorithm for LCS.

Could you please describe this algorithm? I couldn't find enough information on the net!

[srrajesh]

This problem could also be solved by modified Hunt-Szymanski algorithm, an algorithm for LCS.
In this case, you could get the lexicographically smallest palindrome by calculating the lexicographically smallest LCS.

If the algorithm you claimed is not based on the fact that all LCS must be palindromic, then it is ok. The problem with LCS is that, there are some common subsequences which may not be palindromic. I found this thread, discussing on the topic.

[srrajesh]

Thanks a lot, for a good explanation.

[rio]

Could you please describe this algorithm? I couldn't find enough information on the net!

Brief explanation of Hunt-Szymanski algorithm:
For two strings x and y, (i, j) is called match iff x[ i ] = y[ j ].
For two matches (i1, j1) and (i2, j2), (i1, j1) < (i2, j2) iff i1<i2 and j1<j2.
Common sequence of x and y is an increasing sequence of match of x and y.
So LCS problem came down to LIS problem on the match set.
And I think you know that LIS could be solved with O(nlogn).

If the algorithm you claimed is not based on the fact that all LCS must be palindromic, then it is ok. The problem with LCS is that, there are some common subsequences which may not be palindromic.

Yes. The algorithm I'm talking is not simple adaption of LCS on s and reverse s.
To adapt Hunt-Szymanski algorithm to solve palindrome, you have to redefine the match definition.
Also there is a problem to care with the parity of length of the longest palindrome.
But after you get the match set, rest is as same as Hunt-Szymanski.

-----
Rio

[Robert Gerbicz]

I am getting RTE,can any one help?

Robert,how for the input:

Code: Select all

pqrodtkwpfyycjphtijvdnjc

u get:

Code: Select all

dtpaaptd

PLZ expain.I can't see any 'a' in the input string.
Does ur AC code produces this output?

Sorry for that! There was an error in the random generation. (some invalid spaces in the word).