11404  Palindromic Subsequence
Moderator: Board moderators
11404  Palindromic Subsequence
I used DP solution to solve this problem, but I got TLE. It probably take O(n^3) to fill matrix.
[deleted]
any suggestion??
[deleted]
any suggestion??
Last edited by ssangbuja on Mon Feb 25, 2008 9:13 am, edited 2 times in total.

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Re: 11404 Palindromic Subsequence
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 wrote: any suggestion??
Re: 11404 Palindromic Subsequence
Thanks Robert I got AC.Robert Gerbicz wrote: So the total time is O(n^2)

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
There is no special case (but make sure that the word can be very long!).w k wrote:I'm getting WA using DP method. Are there any special inputs for this problem?
Wojciech
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
Code: Select all
h
hh
h
h
bab
bb
bb
abba
aba
a
p
a
a
aba
wyw
wwww
oo
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
Last edited by Robert Gerbicz on Fri Feb 29, 2008 2:46 am, edited 1 time in total.
Re: 11404 Palindromic Subsequence
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?Robert Gerbicz wrote: 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))
Thanks in advance.

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
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[j1], 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[y1].
RTE
I am getting RTE,can any one help?
Robert,how for the input:
u get:
PLZ expain.I can't see any 'a' in the input string.
Does ur AC code produces this output?
Robert,how for the input:
Code: Select all
pqrodtkwpfyycjphtijvdnjc
Code: Select all
dtpaaptd
Does ur AC code produces this output?
My code outputs below for Robert's second input:
This problem could also be solved by modified HuntSzymanski algorithm, an algorithm for LCS.
In this case, you could get the lexicographically smallest palindrome by calculating the lexicographically smallest LCS.

Rio
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
In this case, you could get the lexicographically smallest palindrome by calculating the lexicographically smallest LCS.

Rio
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.rio wrote: This problem could also be solved by modified HuntSzymanski algorithm, an algorithm for LCS.
In this case, you could get the lexicographically smallest palindrome by calculating the lexicographically smallest LCS.
Brief explanation of HuntSzymanski algorithm:Could you please describe this algorithm? I couldn't find enough information on the net!
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).
Yes. The algorithm I'm talking is not simple adaption of LCS on s and reverse s.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.
To adapt HuntSzymanski 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 HuntSzymanski.

Rio
Last edited by rio on Fri Feb 29, 2008 4:57 am, edited 1 time in total.

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Re: RTE
Sorry for that! There was an error in the random generation. (some invalid spaces in the word).Anindya wrote:I am getting RTE,can any one help?
Robert,how for the input:u get:Code: Select all
pqrodtkwpfyycjphtijvdnjc
PLZ expain.I can't see any 'a' in the input string.Code: Select all
dtpaaptd
Does ur AC code produces this output?