0xDE (11011110) wrote,

Counting distinct subsequences

Here's a nice dynamic programming exercise: find a polynomial-time algorithm that takes as input a sequence of n symbols, and a number k, and produces as output the number of distinct k-character subsequences.

For instance, if the input is the string "food" and the number k=2, the output should be 4. There are four distinct two-character subsequences of "food": they are "fo", "fd", "oo", and "od".
Tags: algorithms, dynamic programming
  • Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded  

  • 12 comments