Questions tagged [subsequences]
Questions about algorithms related to subsequences, or about properties of subsequences.
101
questions
2
votes
1
answer
61
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 ...
- 31
0
votes
0
answers
31
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 ...
- 123
0
votes
0
answers
31
views
Is it possible to find Longest common subsequence of all pair of splits of a string in better than $O(n^3)$?
I have a string $a_0a_1..a_{n-1}$
Lets say we split the string at pos $i$, so the string are
$a_0a_1....a_{i}$ and $a_{i+1}a_{i+2}....a_{n-1}$
Now I need to compute:
$max(LCS(a_0a_1....a_{i} , a_{i+1}...
- 111
1
vote
0
answers
26
views
Find if union of discrete intervals with holes covers the whole interval space
There is a whole space interval [0,128]
And several discrete sequences like:
...
1
vote
1
answer
41
views
Hints for efficient computation of the maximum length of a binary sequence
Given a positive integer $n$ I would like to compute $f(n)$, the maximum possible length of a binary sequence such that any substring of it (subsequence with consecutive elements), of length $n$, ...
- 113
1
vote
1
answer
39
views
Finding a 'short' binary sequence not contained in a given binary sequence
Let $k>1$ be an integer, let $n = 2^k$. Let $s: \{0, \ldots, n-1\} \to \{0,1\}$ be any binary sequence of length $n = 2^k$. There are $n - k$ coherent subsequences of $s$ having length $k$, and the ...
1
vote
1
answer
23
views
Matching two noisy / lossy versions of the same data stream to each other
Say I have two noisy / lossy streams of symbols of the same data. Essentially, I want to match up the two streams as best as possible. For example, say I have:
...
- 141
0
votes
1
answer
446
views
Number of subsequence's with same values of bitwise and, or and xor
GeeksForGeeks
We are given an array arr of $n$ element. We need to count number of
non-empty subsequences such that these individual subsequences have
same values of bitwise AND, OR and XOR. For ...
1
vote
0
answers
52
views
Can suffix tree be used to match subsequences?
Given a set of strings, and a pattern - we want to compute the subset of those strings that have that pattern as a subsequence (not substring).
Everything I've read of suffix trees refer to computing ...
4
votes
0
answers
131
views
Sequence where every subset exists as some contiguous subsequence
Given a set (i.e., a collection of distinct elements), how would you find a minimal sequence where every subset of that set can be found as the elements in some contiguous subsequences? The order of ...
- 113
2
votes
1
answer
350
views
Number of subsequence with k distinct characters
"A string is a subsequence of a given string, that is generated by deleting some(possibly zero) character of a given string without changing its order."
Suppose we have string s="aabca&...
- 31
1
vote
1
answer
50
views
How to perform AND on binary "recursive repeating sequences"?
Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related ...
- 71
2
votes
1
answer
132
views
What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence?
I am trying to wrap my head around how dynamic programming helps avoid all possibilities that are exponential after reading Chapter 8 NP-complete problems of Algorithms by Dasgupta et al. where it ...
- 659
1
vote
1
answer
44
views
Sorting in computing longest increasing subsequence
I am currently reading the paper On computing the length of longest increasing subsequences by Michael L. Fredman.
I'm struggling to understand parts of the proof of Theorem 3.5,
especially this bit:
...
1
vote
1
answer
229
views
What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?
Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a
number (possibly one) of continuous parts. For each part independently, I then choose any ...
2
votes
1
answer
660
views
Shortest subsequence containing all elements
Given a sequence $a_1,\ldots,a_n$, find the shortest subsequence $a_i,\ldots,a_j$ such that $\{a_1,\ldots,a_n\} = \{a_i,\ldots,a_j\}$.
I came up with three solutions:
The most straightforward brute-...
- 123
0
votes
0
answers
105
views
Competitive programming: Good Subsets problem
An array of length K is called good if for each subarray of the array, the sum of the subarray is not divisible by K+1. You are given an array A of length N. Find the number of subsequences of length ...
8
votes
1
answer
279
views
Polynomial time algorithm for finding a maximal monotone subset
Input:
Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$.
Output:
A subset $I\subset\{1,\dots,n\}$ of maximal size such that
$(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$.
...
- 131
0
votes
1
answer
62
views
Can we get any subsequence of size $\ge \lfloor \frac{n}{2} \rfloor$ in a sorted order from a sequence in linear time?
Given a sequence $A$ of $N$ distinct integers, does there exist a strategy to get at least one subsequence with size $\geq \lfloor \frac{N}{2} \rfloor$ of the sequence in sorted order in $O(n)$ time?
...
1
vote
4
answers
523
views
Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?
Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less ...
2
votes
1
answer
119
views
Returning random integer from interval based on last result and a seed
Suppose we have an interval of integers [a, b]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are ...
- 31
1
vote
0
answers
34
views
Algorithm to identify rearrangements between two sequences of unique values
I have two sequences, seq1 and seq2, each consisting of unique values. Values can appear in seq1 or seq2 which do not appear in the other, and these values can appear in any order. How do I identify ...
- 111
1
vote
1
answer
289
views
Longest Even-Length Palindromic Subsequence (with distinct adjacent characters except for the center 2 letters)
You are given a string S containing lowercase English characters. You need to find the length of the largest subsequence of S that satisfies the following pattern:
X1,X2,X3...Xn,Xn,...X3,X2,X1
where ...
- 211
1
vote
1
answer
632
views
Can I find all the common subsequences between 2 sequences by using dynamic programming?
I need to know if there's a dynamic programming algorithm that returns all common subsequences between 2 sequences not just the longest one.
Thank you.
- 19
2
votes
1
answer
144
views
Given a list of strings, find every pair $(x,y)$ where $x$ is a subsequence of $y$. Possible to do better than $O(n^2)$?
Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know all pairs $(x,y)$ where $x$ is a subsequence of $y$. We can assume all strings are of ...
1
vote
3
answers
3k
views
Give an efficient dynamic programming algorithm that decides if a string is an interleaving of two other strings
I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book.
You’re consulting for a group of people (who would prefer not to be
mentioned here ...
1
vote
1
answer
144
views
Maximum Subsequence Sum : Mark Weiss:
In the highlighted part below how is Weiss concluding that the array starting at an arbitrary index "p" and ending at "j" can never be larger than the array starting at "i" and ending at "p-1"?
By ...
- 113
9
votes
3
answers
495
views
Test if there exists an integer k to add to one sequence to make it a subsequence of another sequence
Suppose that sequence $A$ contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ and sequence $B$ contains $m$ integers $b_1,b_2,b_3,\ldots,b_m$. We know that $m \geq n$. We assume without loss of generality ...
- 61
1
vote
0
answers
43
views
How to build a set of closed chains with a sequence of different vertices?
I have a set of many bi-directional links like
A-B, A-C, B-C, A-D, C-D, D-E, etc.
I need to find a set of many closed chains with a sequence of different vertices (...
3
votes
0
answers
53
views
Forbidden Sequence Dynamic Programming
Given a finite set $\Omega$, I have the following problem. Say there is a list of forbidden subsequences $F \subset \Omega \cup \Omega^2 \cup \Omega^3 \dots \Omega^\infty$, while we do not know the ...
- 51
1
vote
2
answers
93
views
Sequential subsequence removal with arbitrary predicate
I want to extract sub-sequences from a sequence of float values.
The "scale" and range of these values is arbitrary (as I can manipulate it at will) but the "shape" is consistent.
For a visual ...
- 11
2
votes
1
answer
68
views
Minimize sequence storage by overlapping prefixes
I bumped into this problem today, and after a bit of pondering, I think I have a solution in $O(n^3)$, which is better than no solution or an $O(n!)$ solution, but my answer still isn't great. Can ...
- 173
1
vote
1
answer
648
views
Time complexity of finding subsequences of a string segmented into parts
Let $S$ be a string of length $N$, consisting of digits 0 to 9.
For convenience, we assume $N$ to be a multiple of 3.
Then, we split $S$ into $N/3$ equal parts, each of length 3.
For each equal part,...
- 203
1
vote
1
answer
112
views
ILP representation of the number of maximal 1 sequences in a row
I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some ...
- 976
2
votes
0
answers
209
views
Interleave two arrays such that collisions are minimised (dynamic programming) [closed]
This is a fascinating bioinformatics dynamic programming that I am solving. I am not looking for an answer to the problem, but rather any algorithms, research papers, or other pointers that could be ...
- 21
3
votes
1
answer
964
views
Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised
Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. ...
user102961
2
votes
1
answer
2k
views
Maximum product of contiguous subsequence over $\mathbb{R}$
For the problem of a subsequence of maximum product with negative, zero and positive integers, I have the following working solution (inspiration from here).
Let us first show how to solve the ...
- 123
1
vote
2
answers
408
views
How can I efficiently find the largest positive interval in an unsorted array? [duplicate]
Given a set of values like [4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9], how can I find the largest positive interval between any two of them? For example in the one I just listed, index 0 to index 1 has an ...
0
votes
0
answers
1k
views
Shortest Uncommon Subsequence
Here is another GeeksforGeeks problem that asks how to find the shortest Uncommon Subsequence of 2 strings?
For example,
Input : S = “babab” T = “babba”
Output : 3The subsequence “aab” of ...
- 226
2
votes
0
answers
217
views
Maximize interleaving subsequences two digit arrays/strings
Suppose I have two digit arrays, A and B as follows
A = [3,4,5,6]
B = [9,8,3]
Now, I have ...
- 175
2
votes
0
answers
48
views
How can I optimise a 8b10b encoding for maximum alignment?
Imagine you encode an 8 bit symbol as a 10 bit symbol that is sent sequentially over a wire. The goal at the receiver is to detect the byte boundary.
Since there are 4 times more encoded symbols than ...
- 133
2
votes
1
answer
402
views
Number of contiguous subsequences summing to a given target
I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$.
For ...
- 53
2
votes
1
answer
318
views
How is the Longest Common Sub-sequence of two sequences is a special case of the Sequence Alignment problem?
Could anyone briefly show me how the Longest Common Sub-sequence of two sequences is a special case of the Sequence Alignment problem? I cannot wrap my head around this. Thank you.
- 33
2
votes
1
answer
93
views
longest sub-sequence in both directions
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 ...
- 272
3
votes
0
answers
127
views
Matching relative order in subsequence of fixed length
I encountered this problem from game development which I will formulate in a more formal way:
Given a sequence $A = a_1, a_2, \dots, a_m$ and a permutation of $\{1, \dots, n\}$, $B = b_1, b_2, \...
- 131
5
votes
1
answer
57
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 ...
- 73
1
vote
2
answers
723
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 ...
- 13
1
vote
1
answer
332
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 0`s, 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
42
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(...
