Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\MinSub{\mathsf{MinSub}} \def\LPS{\mathsf{LPS}} \def\LMPS{\mathsf{LMPS}} \def\LCS{\mathsf{LCS}} $

$\MinSub(\sa{bbbbbaeeecffddd},5)=\sa{acddd}$.

$\sa{abba}$ and $\sa{dccd}$ are longest palindromic subsequences of $\sa{dcabcdba}$.

Problem 140: Two longest subsequence problems

There are many problems related to subsequences with specific properties. We consider two simple problems of this type: for a word $x$, compute its lexicographically smallest subsequence of a given length $k$, %denoted by $\MinSub(x,k)$, and a longest palindromic subsequence.

The $\MinSub$ problem

For a word $x$ drawn from an ordered alphabet, $\MinSub(x,k)$ is defined as the lexicographically smallest subsequence of a given length $k$, $k\leq |x|$. Note the subsequence may have several occurrences in $x$.

For a word $x$ of length $n$, design an algorithm that computes $\MinSub(x,k)$ in time $O(n)$.

The $\LPS$ problem

In this second problem, the goal is to compute a longest palindromic subsequence $\LPS(x)$ of the word $x$.

Compute a longest palindromic subsequence of a word of length $n$ in time $O(n^2)$.

125 Problems in Text Algorithms

Example

Problem 140: Two longest subsequence problems

The $\MinSub$ problem

The $\LPS$ problem