Questions tagged [subsequences]

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

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11 votes
1 answer
4k views

Finding the longest repeating subsequence

Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
user avatar
7 votes
1 answer
260 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$. ...
user avatar
  • 121
5 votes
0 answers
368 views

Subarray whose (sum × length) is maximum

Consider the following problem: Given an array of $n$ integer numbers (positive and negative), find a (contiguous) subarray for which the product $(\text{sum of the elements})\times(\text{length ...
user avatar
  • 51
4 votes
0 answers
88 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 ...
user avatar
4 votes
0 answers
157 views

Sequence Alignment with Skips

In my thesis I am working on a problem connected with sequence alignment, in particular, I deal with the Dynamic Time Warping (DTW) algorithm (see this for more), which is used to evaluate the ...
user avatar
3 votes
0 answers
52 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 ...
user avatar
3 votes
0 answers
117 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, \...
user avatar
2 votes
0 answers
213 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 ...
user avatar
2 votes
0 answers
41 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 ...
user avatar
  • 133
1 vote
0 answers
23 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: ...
user avatar
1 vote
0 answers
29 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 ...
user avatar
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 ...
user avatar
  • 111
1 vote
0 answers
42 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 (...
user avatar
1 vote
0 answers
139 views

proving that local sequence alignment can be done in linear space

according to the Smith-Waterman setup, I have 2 string sequences S and T, and I want to identify their respective subsequences $\alpha$ and $\beta$ whose global alignment have maximum score over all ...
user avatar
  • 339
1 vote
0 answers
259 views

Find equal length subsequences with maximum difference of sums, for given maximum subsequence length

The problem is the following. Suppose we have a sequence of n non-negative numbers, each element with index i having its own ...
user avatar
  • 181
1 vote
0 answers
874 views

Longest Increasing Subsequence

I got no responses on stackoverflow, so I'm asking here: How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems? There are a few algorithms, using patience ...
user avatar
  • 1,891
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 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`...
user avatar
  • 121
0 votes
0 answers
28 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}...
user avatar
0 votes
0 answers
86 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 ...
user avatar
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 ...
user avatar
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(...
user avatar
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 ...
user avatar
-1 votes
1 answer
582 views

Check if a string can be split into two subsequences

Given a string S of length N, a string A of length M, a string B of length O such that N >= M + O. Check if the string S can be split into two subsequences X and Y such that A = X and B = Y. Example: ...
user avatar
  • 135