longest sub-sequence in both directions

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.

Example: A = cabca

the sub-sequence S = abc is the longest of such sub-sequences.

reading S forward (abc): cabca

reading S reverse (cba): cabca

How to compute the length of such an S ?

algorithms dynamic-programming strings subsequences

share|cite|improve this question

asked 5 hours ago

user3222

707

add a comment | 

up vote
2
down vote

favorite

Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.

Example: A = cabca

the sub-sequence S = abc is the longest of such sub-sequences.

reading S forward (abc): cabca

reading S reverse (cba): cabca

How to compute the length of such an S ?

algorithms dynamic-programming strings subsequences

share|cite|improve this question

asked 5 hours ago

user3222

707

add a comment | 

up vote
2
down vote

favorite

up vote
2
down vote

favorite

Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.

Example: A = cabca

the sub-sequence S = abc is the longest of such sub-sequences.

reading S forward (abc): cabca

reading S reverse (cba): cabca

How to compute the length of such an S ?

algorithms dynamic-programming strings subsequences

share|cite|improve this question

asked 5 hours ago

user3222

707

Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.

Example: A = cabca

the sub-sequence S = abc is the longest of such sub-sequences.

reading S forward (abc): cabca

reading S reverse (cba): cabca

How to compute the length of such an S ?

algorithms dynamic-programming strings subsequences

algorithms dynamic-programming strings subsequences

share|cite|improve this question

asked 5 hours ago

user3222

707

share|cite|improve this question

asked 5 hours ago

user3222

707

share|cite|improve this question

share|cite|improve this question

asked 5 hours ago

user3222

707

asked 5 hours ago

user3222

707

asked 5 hours ago

user3222

707

707

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
2
down vote

One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.

share|cite|improve this answer

answered 4 hours ago

Yuval Filmus

185k12176336

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for this. Could you give a bigger hint please ?
  – user3222
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Unfortunately it would be difficult for me to give further hints without giving away the solution.
  – Yuval Filmus
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I call it longest 2 sided sub-sequence, the following is my recurrence. | 0 if i>j l2sss(i,j) = | 1 if i = j | 2 + l2sss(i+1, j-1) if s[i]==s[j] //include both | max (2 + l2sss(i+1, find_last_of(s[i])-1), l2sss(i+1, j) two cases within max 1> include s[i], so the problem size become i+1 (because s[i] was included) to find_last_of(s[i]-1) and 2> I exclude s[i]. This does not seem to work (when I implemented this, it does not evaluate to the right answer) and seems to force the string S to be a palindrome (it wasn't a requirement).
  – user3222
  57 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I tried to pretty print that recurrence equation, it did not work out as I expected.
  – user3222
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Could you please tell me what is wrong with my recurrence ?
  – user3222
  24 mins ago
  

  
  
  
  

 | 
show 1 more comment

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f99223%2flongest-sub-sequence-in-both-directions%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote

One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.

share|cite|improve this answer

answered 4 hours ago

Yuval Filmus

185k12176336

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for this. Could you give a bigger hint please ?
  – user3222
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Unfortunately it would be difficult for me to give further hints without giving away the solution.
  – Yuval Filmus
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I call it longest 2 sided sub-sequence, the following is my recurrence. | 0 if i>j l2sss(i,j) = | 1 if i = j | 2 + l2sss(i+1, j-1) if s[i]==s[j] //include both | max (2 + l2sss(i+1, find_last_of(s[i])-1), l2sss(i+1, j) two cases within max 1> include s[i], so the problem size become i+1 (because s[i] was included) to find_last_of(s[i]-1) and 2> I exclude s[i]. This does not seem to work (when I implemented this, it does not evaluate to the right answer) and seems to force the string S to be a palindrome (it wasn't a requirement).
  – user3222
  57 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I tried to pretty print that recurrence equation, it did not work out as I expected.
  – user3222
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Could you please tell me what is wrong with my recurrence ?
  – user3222
  24 mins ago
  

  
  
  
  

 | 
show 1 more comment

up vote
2
down vote

One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.

share|cite|improve this answer

answered 4 hours ago

Yuval Filmus

185k12176336

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for this. Could you give a bigger hint please ?
  – user3222
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Unfortunately it would be difficult for me to give further hints without giving away the solution.
  – Yuval Filmus
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I call it longest 2 sided sub-sequence, the following is my recurrence. | 0 if i>j l2sss(i,j) = | 1 if i = j | 2 + l2sss(i+1, j-1) if s[i]==s[j] //include both | max (2 + l2sss(i+1, find_last_of(s[i])-1), l2sss(i+1, j) two cases within max 1> include s[i], so the problem size become i+1 (because s[i] was included) to find_last_of(s[i]-1) and 2> I exclude s[i]. This does not seem to work (when I implemented this, it does not evaluate to the right answer) and seems to force the string S to be a palindrome (it wasn't a requirement).
  – user3222
  57 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I tried to pretty print that recurrence equation, it did not work out as I expected.
  – user3222
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Could you please tell me what is wrong with my recurrence ?
  – user3222
  24 mins ago
  

  
  
  
  

 | 
show 1 more comment

up vote
2
down vote

up vote
2
down vote

One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.

share|cite|improve this answer

answered 4 hours ago

Yuval Filmus

185k12176336

One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.

share|cite|improve this answer

answered 4 hours ago

Yuval Filmus

185k12176336

share|cite|improve this answer

share|cite|improve this answer

answered 4 hours ago

Yuval Filmus

185k12176336

answered 4 hours ago

Yuval Filmus

185k12176336

answered 4 hours ago

Yuval Filmus

185k12176336

185k12176336

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for this. Could you give a bigger hint please ?
  – user3222
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Unfortunately it would be difficult for me to give further hints without giving away the solution.
  – Yuval Filmus
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I call it longest 2 sided sub-sequence, the following is my recurrence. | 0 if i>j l2sss(i,j) = | 1 if i = j | 2 + l2sss(i+1, j-1) if s[i]==s[j] //include both | max (2 + l2sss(i+1, find_last_of(s[i])-1), l2sss(i+1, j) two cases within max 1> include s[i], so the problem size become i+1 (because s[i] was included) to find_last_of(s[i]-1) and 2> I exclude s[i]. This does not seem to work (when I implemented this, it does not evaluate to the right answer) and seems to force the string S to be a palindrome (it wasn't a requirement).
  – user3222
  57 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I tried to pretty print that recurrence equation, it did not work out as I expected.
  – user3222
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Could you please tell me what is wrong with my recurrence ?
  – user3222
  24 mins ago
  

  
  
  
  

 | 
show 1 more comment

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thanks for this. Could you give a bigger hint please ?
  – user3222
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Unfortunately it would be difficult for me to give further hints without giving away the solution.
  – Yuval Filmus
  2 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  I call it longest 2 sided sub-sequence, the following is my recurrence. | 0 if i>j l2sss(i,j) = | 1 if i = j | 2 + l2sss(i+1, j-1) if s[i]==s[j] //include both | max (2 + l2sss(i+1, find_last_of(s[i])-1), l2sss(i+1, j) two cases within max 1> include s[i], so the problem size become i+1 (because s[i] was included) to find_last_of(s[i]-1) and 2> I exclude s[i]. This does not seem to work (when I implemented this, it does not evaluate to the right answer) and seems to force the string S to be a palindrome (it wasn't a requirement).
  – user3222
  57 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I tried to pretty print that recurrence equation, it did not work out as I expected.
  – user3222
  45 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Could you please tell me what is wrong with my recurrence ?
  – user3222
  24 mins ago
  

  
  
  
  

Thanks for this. Could you give a bigger hint please ?
– user3222
2 hours ago

Thanks for this. Could you give a bigger hint please ?
– user3222
2 hours ago

Unfortunately it would be difficult for me to give further hints without giving away the solution.
– Yuval Filmus
2 hours ago

Unfortunately it would be difficult for me to give further hints without giving away the solution.
– Yuval Filmus
2 hours ago

I call it longest 2 sided sub-sequence, the following is my recurrence. | 0 if i>j l2sss(i,j) = | 1 if i = j | 2 + l2sss(i+1, j-1) if s[i]==s[j] //include both | max (2 + l2sss(i+1, find_last_of(s[i])-1), l2sss(i+1, j) two cases within max 1> include s[i], so the problem size become i+1 (because s[i] was included) to find_last_of(s[i]-1) and 2> I exclude s[i]. This does not seem to work (when I implemented this, it does not evaluate to the right answer) and seems to force the string S to be a palindrome (it wasn't a requirement).
– user3222
57 mins ago

I call it longest 2 sided sub-sequence, the following is my recurrence. | 0 if i>j l2sss(i,j) = | 1 if i = j | 2 + l2sss(i+1, j-1) if s[i]==s[j] //include both | max (2 + l2sss(i+1, find_last_of(s[i])-1), l2sss(i+1, j) two cases within max 1> include s[i], so the problem size become i+1 (because s[i] was included) to find_last_of(s[i]-1) and 2> I exclude s[i]. This does not seem to work (when I implemented this, it does not evaluate to the right answer) and seems to force the string S to be a palindrome (it wasn't a requirement).
– user3222
57 mins ago

Sorry, I tried to pretty print that recurrence equation, it did not work out as I expected.
– user3222
45 mins ago

Sorry, I tried to pretty print that recurrence equation, it did not work out as I expected.
– user3222
45 mins ago

Could you please tell me what is wrong with my recurrence ?
– user3222
24 mins ago

Could you please tell me what is wrong with my recurrence ?
– user3222
24 mins ago

 | 
show 1 more comment

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f99223%2flongest-sub-sequence-in-both-directions%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email