Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [subsequences]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
48 views

Is "Length of Longest Increasing Subsequence" in L?

I can't find space complexity of this problem with search engines. I think I have NL algorithm for it (just a basic "one by one non-deterministically accept values if possible"), but I ...
Noone AtAll's user avatar
1 vote
1 answer
64 views

longest symmetric sequence

Suppose we are given a $n$-vector $A$ of real numbers. We need to find the longest sequence of symmetrical numbers. The numbers $a_i$ and $a_j$ are symmetrical if they are located at the same distance ...
Nick's user avatar
  • 175
3 votes
1 answer
96 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 ...
popcorn's user avatar
  • 183
0 votes
0 answers
32 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 ...
Julius Hamilton's user avatar
0 votes
0 answers
32 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}...
ishandutta2007's user avatar
1 vote
0 answers
27 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: ...
Alexandr Dorofeev's user avatar
1 vote
1 answer
46 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$, ...
Fabius Wiesner's user avatar
1 vote
1 answer
47 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 ...
Dominic van der Zypen's user avatar
1 vote
1 answer
26 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: ...
Mala's user avatar
  • 141
0 votes
1 answer
481 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 ...
Devesh jha's user avatar
1 vote
0 answers
60 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 ...
Sridhar Ratnakumar's user avatar
4 votes
0 answers
146 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 ...
magnetlion's user avatar
2 votes
1 answer
384 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&...
code_it's user avatar
  • 31
1 vote
1 answer
53 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 ...
komorra's user avatar
  • 71
2 votes
1 answer
138 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 ...
heretoinfinity's user avatar
1 vote
1 answer
47 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: ...
adriankroeger's user avatar
1 vote
1 answer
237 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 ...
Powerful blaster's user avatar
2 votes
1 answer
753 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-...
kirilloid's user avatar
  • 123
0 votes
0 answers
107 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 ...
Anurag chaudhary's user avatar
9 votes
1 answer
285 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$. ...
Klaas's user avatar
  • 141
0 votes
1 answer
64 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? ...
Arkajyoti Banerjee's user avatar
1 vote
4 answers
588 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 ...
Arkajyoti Banerjee's user avatar
2 votes
1 answer
120 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 ...
sn0wtroopeer's 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 ...
brainkim's user avatar
  • 111
1 vote
1 answer
298 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 ...
Sid's user avatar
  • 211
1 vote
1 answer
702 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.
user118909's user avatar
2 votes
1 answer
156 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 ...
securitymensch's user avatar
1 vote
3 answers
4k 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 ...
Pritesh Singh's user avatar
1 vote
1 answer
168 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 ...
user152810's user avatar
9 votes
3 answers
499 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 ...
iouvxz's user avatar
  • 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 (...
Alex Shnaider's user avatar
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 ...
Zach Hunter's user avatar
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 ...
stephenjfox's user avatar
2 votes
1 answer
76 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 ...
Sean Werkema's user avatar
1 vote
1 answer
659 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,...
yoyostein's user avatar
  • 203
1 vote
1 answer
117 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 ...
Throckmorton's user avatar
2 votes
0 answers
212 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 ...
Daniel's user avatar
  • 21
3 votes
1 answer
990 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. ...
user avatar
3 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 ...
silviubogan's user avatar
1 vote
2 answers
459 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 ...
temporary_user_name's 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 ...
asn's user avatar
  • 226
2 votes
0 answers
218 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 ...
Palash Ahuja's user avatar
2 votes
0 answers
52 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 ...
Pepijn's user avatar
  • 133
2 votes
1 answer
441 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 ...
Iris's user avatar
  • 53
2 votes
1 answer
323 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.
TypeR's user avatar
  • 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 ...
rranjik's user avatar
  • 284
3 votes
0 answers
132 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, \...
Jingjie Yang's user avatar
5 votes
1 answer
58 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 ...
Daniel Ong's user avatar
1 vote
2 answers
735 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 ...
Yashit Garg's user avatar
1 vote
1 answer
341 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`...
Xhark's user avatar
  • 121