Stack Overflow
Stack Overflow

Questions tagged [subsequence]

A subsequence is a sequence obtained by deleting some elements and retaining the relative order of the remaining elements. It is a generalization of substring which contains only consecutive elements of the original sequence.

A subsequence is a sequence obtained by deleting some elements and retaining the relative order of the remaining elements. It is a generalization of substring which contains only originally consecutive elements.

303 questions
58
votes
10 answers

Difference between subarray, subset & subsequence

I'm a bit confused between subarray, subsequence & subset if I have {1,2,3,4} then subsequence can be {1,2,4} OR {2,4} etc. So basically I can omit some elements but keep the order. subarray would be( say subarray of size 3) {1,2,3} {2,3,4}…
user2821242
  • 1,041
  • 3
  • 9
  • 16
37
votes
9 answers

What is the difference between String.subString() and String.subSequence()

String.subSequence() has the following javadoc: Returns a new character sequence that is a subsequence of this sequence. An invocation of this method of the form str.subSequence(begin, end) behaves in exactly the same way as the invocation …
124697
  • 22,097
  • 68
  • 188
  • 315
35
votes
44 answers

Given a list of numbers and a number k, return whether any two numbers from the list add up to k

This question was asked in the Google programming interview. I thought of two approaches for the same: Find all the subsequences of length. While doing so compute the sum and of the two elements and check if it is equal to k. If ye, print Yes, else…
Jhanak Didwania
  • 581
  • 2
  • 5
  • 12
17
votes
5 answers

Number of all longest increasing subsequences

I'm practicing algorithms and one of my tasks is to count the number of all longest increasing sub-sequences for given 0 < n <= 10^6 numbers. Solution O(n^2) is not an option. I have already implemented finding a LIS and its length (LIS Algorithm),…
Wojciech Kulik
  • 7,823
  • 6
  • 41
  • 67
16
votes
3 answers

Searching a minimal string meeting some conditions

Recently, I was asked the following problem during an interview. Given a string S, I need to find another string S2 such that S2 is a subsequence of S and also S is a subsequence of S2+reverse(S2). Here '+' means concatenation. I need to output the…
LTim
  • 473
  • 1
  • 4
  • 15
12
votes
2 answers

Understanding the time complexity of the Longest Common Subsequence Algorithm

I do not understand the O(2^n) complexity that the recursive function for the Longest Common Subsequence algorithm has. Usually, I can tie this notation with the number of basic operations (in this case comparisons) of the algorithm, but this time…
Daniel Catita
  • 227
  • 1
  • 2
  • 7
11
votes
2 answers

How does OEIS do subsequence search?

The Online Encyclopedia of Integer Sequences supports search for sequences containing your query as a subsequence, eg. searching for subseq:212,364,420,428 will return the 8*n+4 sequence. (http://oeis.org/search?q=subseq:212,364,420,428) This…
Thomas Ahle
  • 30,774
  • 21
  • 92
  • 114
10
votes
1 answer

Longest Palindromic Subsequence (dp solution)

Among several dp solutions for this question, an easier solution is to reverse the given string and calculate LCS of the original and reversed string. My question is will this approach yield correct result every time ? For instance , a longest…
Julkar9
  • 1,508
  • 1
  • 12
  • 24
8
votes
2 answers

Is there any O(n^2) algorithm to generate all sub-sequences of an array?

I was wondering if there is any O(n^2) complexity algorithm for generating all sub-sequences of an array. I know an algorithm but it takes O((2^n)*n) time. int main() { int n; cin >> n; vector a(n); for(int i = 0; i < n; ++i) …
Naimish Singh
  • 83
  • 1
  • 4
8
votes
1 answer

Longest Repeated (non-overlapping) Subsequence

How to find the longest repeated (non-overlapping) subsequence (not substring)? constraint: The string S consist of at most 100.000 lower case character 'a'-'z'. example: String hanadswomehanudsiome has longest repeated (non-overlapping) …
Dewangga Winardi
  • 119
  • 6
7
votes
3 answers

Is there any difference at all between suffix(from:) and dropFirst(_:)?

It just occurred to me that when working with subsequences in Swift, func suffix(from: Int) seems to be identical to just dropFirst(_:) (Obviously, you just change the input value from say "3" to "7" in the case of an array of length "10".) Just to…
Fattie
  • 27,874
  • 70
  • 431
  • 719
7
votes
3 answers

Common subsequence of given length

What are good ways to find all the common subsequences of length k of two strings? Example: s1= AAGACC s2= AGATAACCAGGAGCTGC all common subsequences of length 5: AAGAC AAACC AGACC AAGCC
Camilo Celis Guzman
  • 595
  • 1
  • 5
  • 17
7
votes
4 answers

Check if string is substring in Prolog

Is there a way to check if a string is a substring of another string in Prolog? I tried converting the string to a list of chars and subsequently checking if the first set is a subset of the second that that doesn't seem to be restrictive enough.…
MaVe
  • 1,715
  • 5
  • 21
  • 29
6
votes
1 answer

Vectorization or efficient way to calculate Longest Increasing subsequence of tuples with Pandas

Using pandas/python, I want to calculate the longest increasing subsequence of tuples for each DTE group, but efficiently with 13M rows. Right now, using apply/iteration, takes about 10 hours. Here's roughly my…
Erich Lin
  • 105
  • 5
6
votes
1 answer

How to find longest constrained subsequence

Given an array which contains N different integers, find the longest subsequence which satisfies: the start element of the subsequence is the smallest of the subsequence. the end element of the subsequence is the largest of the…
Amos
  • 3,238
  • 4
  • 19
  • 41
1
2 3
…
20 21