Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [subsequences]

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

1
vote
1answer
61 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
45 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
70 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
87 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
13 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
44 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
101 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
39 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
73 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
45 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
400 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
99 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
239 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
25 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
61 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
54 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
397 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
301 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
68 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
81 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
121 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
51 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
588 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
184 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
668 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
160 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
99 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
736 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$ ...
0
votes
0answers
518 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 ...
3
votes
1answer
302 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 ...
0
votes
1answer
48 views

Finding a subarray of time series data in which all values are less than X for specified time Y?

The idea is to find an anomalous value (i.e. it's less than X) in time series data (sorted by time), and check if this behavior continues during specified time (Y=2 hours). If all values in sub-array ...
2
votes
1answer
778 views

Algorithm to identify if a string of numbers is a lottery sequence

Suppose that a valid lottery ticket consists of a sequence of 7 numbers drawn from the set $\{1,2,\ldots,59\}$. Given a string like "$12345678$", I want to efficiently print all the lottery sequences ...
4
votes
0answers
107 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 ...
1
vote
0answers
68 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 ...
3
votes
2answers
138 views

How to efficiently code Dynamic Time Warping algorithm with a locality constrain?

For given two lists $[s_1, s_2, ... s_n]$ and $[t_1, t_2, ..., t_m]$ I need to implement DTW algorithm with one extra constraint: If $s_i$ is matched with $t_j$ then the next element $s_{i+1}$ has ...
1
vote
0answers
205 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 ...
1
vote
0answers
271 views

Proof that the length of the largest ascending subsequence is the number of decreasing subsequences

Given a sequence of numbers, I have to prove that the number of decreasing subsequences (non-strictly), so that every number is included in one subsequence and the number of subsequences is minimum is ...
1
vote
2answers
396 views

Find long connected similar subsequences in two given sequences

I'm looking for pointers to algorithms which will find long connected similar subsequences which two given sequences have in common. For example, in case of two strings: ...
2
votes
1answer
411 views

How is n-gram different from k-mer?

How is n-gram different from k-mer? Both seem to be (n or k) length substrings of a larger string. Are these just terms common with different practitioners? viz. Computer Scientists and ...
3
votes
1answer
273 views

Remove contiguous subsequence so the remaining numbers will created a sorted sequence

You are given $N$ numbers. Remove contiguous subsequence of those numbers, so the remaining numbers will create a sorted sequence. For example, if the sequence is $5$, $7$, $8$, $2$, $1$, $9$ then we ...
4
votes
1answer
393 views

Counting the number of permutations of string with given repeated interwoven subsequence

Given string $S$ of length $n$, count the number of distinct permutations $P_n$ of a string of length $2n$ such that each of them contains $S$ twice as an interwoven subsequence. Example. $S=abc$. ...
9
votes
1answer
3k 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$ ...
-1
votes
1answer
201 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: ...
6
votes
1answer
2k views

Computing the mode of XOR subsequences

I was confronted with this problem in an online programming challenge and it has been bugging me since: In the problem, you are given a list of 16-bit numbers, say $a_0, a_1, ..., a_n$. An "XOR ...
3
votes
1answer
263 views

Longest “bounded” subsequence

Given a sequence of comparable objects $a_1, a_2, \ldots a_n,$ how quickly can we find the longest subsequence $s$ such that $s_i > s_1$ for $i > 1$? Or equivalently, how quickly can we find $$...
4
votes
2answers
2k views

Maximum sum subset of an array with an extra condition

We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every ...
1
vote
1answer
137 views

Algorithm to merge two incomplete lists of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution. Let's say we have two ordered lists of symbols (strings): ...
22
votes
2answers
2k views

Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
5
votes
0answers
350 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 ...
3
votes
2answers
3k views

Detecting a subsequence that's an arithmetic progression, in a sorted sequence

I have following problem: I have a sorted sequence of $N$ integers (assume they are monotonically increasing). I want to check whether there is any subsequence of length $\ge N/4$, such that ...