The 2024 Developer Survey results are live! See the results

# Questions tagged [subsequences]

103 questions
Filter by
Sorted by
Tagged with
56 views

### Is "Length of Longest Increasing Subsequence" in L?

I can't find space complexity of this problem with search engines. I think I have NL algorithm for it (just a basic "one by one non-deterministically accept values if possible"), but I ...
• 245
1 vote
68 views

### longest symmetric sequence

Suppose we are given a $n$-vector $A$ of real numbers. We need to find the longest sequence of symmetrical numbers. The numbers $a_i$ and $a_j$ are symmetrical if they are located at the same distance ...
• 175
108 views

### Longest Fibonacci word

We define Fibonacci words as: $F_0 = a, F_1 = b, F_{n+2} = F_n F_{n+1}$, $a, b$ can be any symbols. How can we find the longest Fibonacci sub-word in a given string in linear time? This question is ...
• 183
32 views

### Analysis of this (palindrome) sequence

This may be a simple problem ultimately. I am picturing a “rule” of “relative enumeration”. Let’s say you start with “19”. This means, there was another choice you missed - implying that you will ...
32 views

• 131
59 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
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...