# Questions tagged [subsequences]

93 questions
Filter by
Sorted by
Tagged with
71 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 ...
48 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&...
38 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 ...
17 views

### Predictive score ? how?

let say I have a sequence of values ... The values X and Y can be either number or data structures or states ... and so on ... Example: Value X can be followed by any of "n" other values Y1,...
106 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 ...
17 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: ...
79 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 ...
342 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-...
58 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 ...
230 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$. ...
56 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? ...
181 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 ...
88 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 ...
33 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 ...
189 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 ...
288 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.
72 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 ...
1k 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 ...
63 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 ...
304 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 ...
38 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 (...
48 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 ...
76 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 ...
36 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 ...
382 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,...
70 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 ...
202 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 ...
803 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. ...
1k 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 ...
89 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 ...
805 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 ...
208 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 ...
31 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 ...
163 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 ...
255 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.
69 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 ...
105 views

91 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 ...
473 views

### Number of possible sequence partitioning

Given a sequence of 1 and 0 elements, what is the number of possible partitioning of the sequence in sub-sequences (not necessarily consecutive elements, and any number of sub-sequences are allowed) ...