## 11404 - Palindromic Subsequence

Moderator: Board moderators

ssangbuja
New poster
Posts: 2
Joined: Sun Feb 24, 2008 9:22 am

### 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??
Last edited by ssangbuja on Mon Feb 25, 2008 9:13 am, edited 2 times in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 11404 Palindromic Subsequence

ssangbuja wrote: 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
New poster
Posts: 2
Joined: Sun Feb 24, 2008 9:22 am

### Re: 11404 Palindromic Subsequence

Robert Gerbicz wrote: So the total time is O(n^2)
Thanks Robert I got AC.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
I'm getting WA using DP method. Are there any special inputs for this problem?

Wojciech

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:
w k wrote: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
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!
Last edited by Robert Gerbicz on Fri Feb 29, 2008 2:46 am, edited 1 time in total.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
OK. I got it.

Wojciech

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

### Re: 11404 Palindromic Subsequence

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))
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?

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
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[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
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

### RTE

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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
rio wrote: 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
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm
rio wrote: 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
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm
Thanks a lot, for a good explanation.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
Last edited by rio on Fri Feb 29, 2008 4:57 am, edited 1 time in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: RTE

Anindya wrote: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).