# Questions tagged [subsequences]

99 questions
Filter by
Sorted by
Tagged with
29 views

• 131
56 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
699 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
317 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
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
39 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
### 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(...