Questions tagged [subsequences]

Questions about algorithms related to subsequences, or about properties of subsequences.

99 questions
Filter by
Sorted by
Tagged with
0 votes
0 answers
28 views

• 131
5 votes
1 answer
54 views

How can I efficiently generate the shortest list of arguments for the range() function that will generate a given list of integers?

I ran into an interesting problem at work when trying to generate the inputs for an API given the expected output. I've tried to formalize and anonymize the problem below. I've been trying to design a ...
1 vote
2 answers
662 views

Counting number of perfect squares in an subarrays

A sequence is good if the bitwise AND of all its elements is a perfect square. So counting number of "good" sequences, in a subarray . For example : in [1, 2, 3] There are 6 sub-sequences: So ...
1 vote
1 answer
312 views

DFA for strings with number of 0's odd only in substring longer than 1

I'm trying to design and DFA that accept string with an odd number of 0s, but counting only the ones within sub-strings with two or more 0. So, for example, 011000, will be accepted since it has 4 0...
• 121
0 votes
1 answer
1k views

Complexity of Longest Palindromic Subsequence Algorithm

I'm trying to find the longest palindromic subsequence for any string and I've tried two approaches: Recursive Algoritm Dynamic Programming Dynamic programming should be the better option in this ...
• 103
0 votes
0 answers
34 views

How many optimal alignments can be there for a string of length m with a string of length n?

So I was practicing optimal alignment algorithm and I was stuck with this question of finding optimal alignment for a string of length m with a string length n ? Also is it possible to run it in theta(...
1 vote
1 answer
72 views

How to check if $m$ numbers in a sequence satisfy a condition, such that all these numbers are spaced apart by at least $k$?

Suppose we have a sequence $s$ with $n$ elements from $s[1..n]$. I want to check if there exists $m \leq n$ elements in this sequence that each satisfy some simple condition (that can be tested in \$O(...
0 votes
0 answers
100 views

Activity planning problem

Given a sequence of N activity durations, the time P of pause between activities, and D, the length of a day (there are no breaks between days, only between activities in a day), what is the minimum ...