Questions tagged [subsequences]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
48 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 ...
7
votes
1answer
206 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$. ...
0
votes
1answer
46 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
4answers
144 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
1answer
73 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 ...
1
vote
0answers
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 ...
1
vote
1answer
72 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 ...
0
votes
1answer
103 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.
2
votes
1answer
47 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
3answers
518 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
1answer
50 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 ...
9
votes
3answers
295 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 ...
1
vote
0answers
36 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
0answers
46 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 ...
1
vote
2answers
71 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 ...
2
votes
1answer
33 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 ...
1
vote
1answer
220 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,...
1
vote
1answer
62 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 ...
2
votes
0answers
198 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 ...
3
votes
1answer
634 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. ...
1
vote
1answer
930 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 ...
1
vote
2answers
57 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
0answers
647 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 ...
2
votes
0answers
201 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 ...
2
votes
0answers
29 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 ...
1
vote
1answer
107 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 ...
2
votes
1answer
247 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.
2
votes
1answer
56 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 ...
3
votes
0answers
93 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, \...
5
votes
1answer
46 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
2answers
650 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
1answer
218 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`...
0
votes
1answer
772 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 ...
0
votes
0answers
29 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
1answer
67 views

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(...
0
votes
0answers
82 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 ...
1
vote
1answer
459 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) ...
3
votes
2answers
736 views

Count the unique subsequences

I'm trying to count the number of subsequences of a long string. e.g. BANANA -> B, A, N, BA, BN, AA, NN, NA, BAN, BAA, BNA, BNN, ANA, AAA, NAN, NNA, etc There's the horribly inefficient way, which ...
1
vote
1answer
84 views

Finding a (Small-Big-Medium) subsequence

Given a list of $n$ non repeating integer numbers $L:=(x_1,\dots,x_n)$ develop an algorithm that decides if there are $x_{i_1},x_{i_2},x_{i_3}\in L$ such that $i_1<i_2<i_3$ and $x_{i_1}<x_{...
3
votes
1answer
151 views

Find the longest contigous subsequence where each pair's difference is at most p

Given input sequence $x_1,...,x_n$, find the longest contigous subsequence $x_i,... x_l$ where each pair $(x_j,x_k)$ satisfies that $|x_j - x_k| \le p$. I have come up with simple $\mathcal{O}(n^2)$ ...
3
votes
1answer
288 views

Shortest Non-Subsequence String With Constant-Size Alphabet

Let $S[1..n] \in \Sigma^*$ be a string of $n$ symbols over the alphabet $\Sigma$ where $|\Sigma| \in \mathcal{O}(1)$. Determine a shortest string which cannot be obtained from $S$ by deleting some (...
2
votes
1answer
151 views

Implementing SUM(i,j) and CHANGE(i,j) in O(log(n)) using a datastructure with O(n) space complexity

I have two operations: $Sum(i,j)$ : Calculate $A[i]+A[i+1]+....+A[j]$ $Change(i,x)$: Set $A[i]=x$ I need to implement these operations in an appropriate data structure using $O(n)$ space ($n$ is ...
3
votes
2answers
1k views

Find longest subsequence in array with given condition

I am given an array $A$ having $n$ elements and an integer $k$. I need to find the longest subsequence which always includes the first element and the subsequence follows the given condition: for ...
4
votes
1answer
359 views

Why does Banded Needleman-Wunsch give alignments with no more than d base pairs of indels?

A common modification to the Needleman-Wunsch to reduce running time is to only fill in the cells along a diagonal band of the matrix (slides 27/28). Let 2d + 1 represent the width of the band. Then ...
2
votes
1answer
1k views

How to count all contiguous subsequences with positive sum?

I have array $t$ with size $n \leq 10^6$. It has only two kinds of elements inside: $1$ or $-1$. I need to count how many contiguous subsequences have positive sum. This pseudocode demonstrates ...
1
vote
1answer
306 views

Longest increasing subsequence on pairs

Given a sequence of pairs $(a_1, b_1), (a_2, b_2), ..., (a_n, b_n)$ such that $a_1 \le a_2 \le ... \le a_n$ (i.e, sorted in ascending order by $a$'s), we solve the longest increasing subsequence ...
7
votes
1answer
115 views

Subsequence of one string but not of others

Let $\Sigma$ be an alphabet, and let $x^+,x^-_1,\dots,x^-_n \in \Sigma^*$ be strings over that alphabet. Call a string $s \in \Sigma^*$ good if $s$ is a subsequence of $x^+$ but not a subsequence of ...
7
votes
2answers
1k views

Count of distinct substrings in string inside range

Having string $S$ of length $n$, finding the count of distinct substrings can be done in linear time using LCP array. Instead of asking for unique substrings count in whole string $S$, query $q$ ...
2
votes
1answer
1k views

ZigZag sequence without dynamic programming

I just came across the maximum zigzag sequence problem, defined as follows: A zigzag sequence is defined as a sequence of numbers such that the difference between two consecutive numbers alternates ...
2
votes
1answer
341 views

Longest common subsequence of a set of sequences

There is as input a set of $m$ sequences of length $n$. I thought it was pretty straightforward at first that the time complexity of the algorithm provided below is $O(m^2n^4)$ but then it occurred ...