# Tagged Questions

The tag has no usage guidance.

49 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 ...
54 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 ...
91 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$. ...
278 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$ ...
64 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: ...
1k 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 ...
177 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 ...
394 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 ...
56 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): ...
927 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 ...
248 views

207 views

### Find the longest subsequence of two strings

I want to know which is the best way to find the longest common subsequence of two strings
675 views

### Finding the longest common subsequence algorithm using hash table Slow

I've designed an algorithm to find the longest common subsequence. these are steps: Starts with i = 0 Picks the first letter from the first string start from ...
2k views

### Count unique increasing subsequences of length 3 in $O(n\log n)$

Problem: Given an array of $n$ integers, $A[1 \dots n]$, such that any integer occurs at most 2 times in the array, we have to find the number of unique increasing subsequences of length 3 (duplicate ...
111 views

### Improving Time Bound of this Algorithm past $O(n^2)$

I recently came across the following interesting problem - one is given a sequence of Xs and Ys such as ...
4k views

### Find the longest repeated pattern in a string

I'm looking for an efficient algorithm to find the longest repeated pattern in a string. For example, consider the following string of numbers: ...
49 views

### Longest range with sum smaller than K [duplicate]

Possible Duplicate: Dynamic programming table for finding similar substrings is too large Say I have a sequence $S$ of 0s and 1s such as $S = [1, 0, 0, 1, 0, 1]$ How would I efficiently find ...
455 views

### Longest Increasing Subsequence

I got no responses on stackoverflow, so I'm asking here: How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems? There are a few algorithms, using patience ...
6k views

### Fastest algorithm for finding the longest palindrome subsequence

First of all we must read a word, and a desired size. Then we need to find the longest palindrome created by characters in this word used in order. For example for size = 7 and word = "abcababac" the ...
983 views

### How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?

You are given n integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a non-...
712 views

### How to output all longest decreasing sequences

Suppose I have an array of integers having length $N$. How can I output all longest decreasing sequences? (A subsequence consists of elements of the array that do not have to be consecustive, for ...
We are given a set $F=\{f_1, f_2, f_3, …, f_N\}$ of $N$ Fruits. Each Fruit has price $P_i$ and vitamin content $V_i$; we associated fruit $f_i$ with the ordered pair $(P_i, V_i)$. Now we have to ...
### Is there an algorithm which finds sorted subsequences of size three in $O(n)$ time?
I want to prove or disprove the existence of an algorithm which, given an array $A$ of integers, finds three indices $i, j$ and $k$ such that $i < j < k$ and $A[i] < A[j] < A[k]$ (or finds ...