# Distinct subsequences using dynamic programming

In computer science, the problem of finding the number of distinct subsequences in a given sequence that match a given word is a common task. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. This problem can be efficiently solved using dynamic programming techniques.

## Problem Statement

Given a sequence and a word, we need to find the number of distinct subsequences in the sequence that match the given word. In other words, we need to count how many times we can form the word by deleting characters from the sequence while maintaining the relative order of the characters.

For example, consider the sequence "initcometipe" and the word "ice". In this case, there are four distinct subsequences of the sequence that match the word "ice": "initcometipe", "initcometipe", "initcometipe", and "initcometipe".

## Approach and Algorithm

We can solve this problem using dynamic programming. Let's denote the length of the sequence as n and the length of the word as m. We will use a 2D array `dp` of size (n+1) x (m+1), where `dp[i][j]` represents the number of distinct subsequences of the first i characters of the sequence that match the first j characters of the word.

The dynamic programming algorithm consists of the following steps:

1. Initialize the first column of `dp` with 1, as there is only one way to form an empty word from any prefix of the sequence.
2. Iterate over each character in the sequence (from left to right) using two nested loops. Let's denote the current character in the sequence as `sequence[i]`.
3. For each character `sequence[i]`, iterate over each character in the word (from left to right) using another nested loop. Let's denote the current character in the word as `word[j]`.
4. If `sequence[i]` is equal to `word[j]`, it means we can consider the current character `sequence[i]` as part of the subsequence that matches `word[j]`. In this case, we update `dp[i+1][j+1]` as the sum of two values: `dp[i][j]` (the number of distinct subsequences without considering the current character) and `dp[i][j+1]` (the number of distinct subsequences considering the current character).
5. If `sequence[i]` is not equal to `word[j]`, it means we cannot consider the current character `sequence[i]` as part of the subsequence that matches `word[j]`. In this case, we update `dp[i+1][j+1]` as the same value as `dp[i][j+1]` (the number of distinct subsequences considering the current character).
6. After the loops, the value in `dp[n][m]` represents the number of distinct subsequences of the entire sequence that match the entire word.

## Pseudocode

Here is the pseudocode for the algorithm:

``````distinctSubsequences(sequence, word):
n = length of sequence
m = length of word
create a 2D array dp of size (n+1) x (m+1)
initialize dp = 1 and dp[i] = 1 for i = 1 to n

for i = 0 to n-1:
for j = 0 to m-1:
if sequence[i] == word[j]:
dp[i+1][j+1] = dp[i][j] + dp[i][j+1]
else:
dp[i+1][j+1] = dp[i][j+1]

print "Sequence: " + sequence
print "Word: " + word
print "Result: " + dp[n][m]
``````

## Code Solution

``````// C Program
// Distinct subsequences using dynamic programming
#include <stdio.h>

#include <string.h>

void distinctSubsequences(char *sequence, char *word)
{
// Get the length of sequence
int n = strlen(sequence);
// Get the length of word
int m = strlen(word);
int dp[n + 1][m + 1];
// Set initial value of first column
for (int i = 0; i <= n; ++i)
{
dp[i] = 1;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (sequence[i] == word[j])
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
}
}
// Display given data
printf("\n Sequence : %s ", sequence);
printf("\n Word : %s", word);
// Display calculated result
printf("\n Result : %d", dp[n][m]);
}
int main()
{
char *sequence = "initcometipe";
char *word = "ice";
/*
sequence : initcometipe
word     : ice
------------------
initcometipe
-   -  -        ➀ [ice]

initcometipe
-   -      -    ➁ [ice]

initcometipe
- -  -        ➂ [ice]

initcometipe
- -      -    ➃ [ice]
-------------------------------
4 possible sequence
*/
distinctSubsequences(sequence, word);
return 0;
}``````

#### Output

`````` Sequence : initcometipe
Word : ice
Result : 4``````
``````// Java program for
// Distinct subsequences using dynamic programming
public class Subsequence
{
public void distinctSubsequences(String sequence, String word)
{
// Get the length of sequence
int n = sequence.length();
// Get the length of word
int m = word.length();
int[][] dp = new int[n + 1][m + 1];
// Set initial value of first column
for (int i = 0; i <= n; ++i)
{
dp[i] = 1;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (sequence.charAt(i) == word.charAt(j))
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
}
}
// Display given data
System.out.print("\n Sequence : " + sequence);
System.out.print("\n Word : " + word);
// Display calculated result
System.out.print("\n Result : " + dp[n][m]);
}
public static void main(String[] args)
{
String sequence = "initcometipe";
String word = "ice";
/*
sequence : initcometipe
word     : ice
------------------
initcometipe
-   -  -        ➀ [ice]

initcometipe
-   -      -    ➁ [ice]

initcometipe
- -  -        ➂ [ice]

initcometipe
- -      -    ➃ [ice]
-------------------------------
4 possible sequence
*/
}
}``````

#### Output

`````` Sequence : initcometipe
Word : ice
Result : 4``````
``````// Include header file
#include <iostream>

#include <string>

using namespace std;
// C++ program for
// Distinct subsequences using dynamic programming
class Subsequence
{
public: void distinctSubsequences(string sequence, string word)
{
// Get the length of sequence
int n = sequence.length();
// Get the length of word
int m = word.length();
int dp[n + 1][m + 1];
// Set initial value of first column
for (int i = 0; i <= n; ++i)
{
dp[i] = 1;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (sequence[i] == word[j])
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
}
}
// Display given data
cout << "\n Sequence : " << sequence;
cout << "\n Word : " << word;
// Display calculated result
cout << "\n Result : " << dp[n][m];
}
};
int main()
{
string sequence = "initcometipe";
string word = "ice";
/*
sequence : initcometipe
word     : ice
------------------
initcometipe
-   -  -        ➀ [ice]

initcometipe
-   -      -    ➁ [ice]
initcometipe
- -  -        ➂ [ice]

initcometipe
- -      -    ➃ [ice]
-------------------------------
4 possible sequence
*/
return 0;
}``````

#### Output

`````` Sequence : initcometipe
Word : ice
Result : 4``````
``````// Include namespace system
using System;
// Csharp program for
// Distinct subsequences using dynamic programming
public class Subsequence
{
public void distinctSubsequences(String sequence, String word)
{
// Get the length of sequence
int n = sequence.Length;
// Get the length of word
int m = word.Length;
int[,] dp = new int[n + 1,m + 1];
// Set initial value of first column
for (int i = 0; i <= n; ++i)
{
dp[i,0] = 1;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (sequence[i] == word[j])
{
// Change value when sequence contains word element
dp[i + 1,j + 1] = dp[i,j] + dp[i,j + 1];
}
else
{
dp[i + 1,j + 1] = dp[i,j + 1];
}
}
}
// Display given data
Console.Write("\n Sequence : " + sequence);
Console.Write("\n Word : " + word);
// Display calculated result
Console.Write("\n Result : " + dp[n,m]);
}
public static void Main(String[] args)
{
String sequence = "initcometipe";
String word = "ice";
/*
sequence : initcometipe
word     : ice
------------------
initcometipe
-   -  -        ➀ [ice]

initcometipe
-   -      -    ➁ [ice]
initcometipe
- -  -        ➂ [ice]

initcometipe
- -      -    ➃ [ice]
-------------------------------
4 possible sequence
*/
}
}``````

#### Output

`````` Sequence : initcometipe
Word : ice
Result : 4``````
``````package main
import "fmt"
// Go program for
// Distinct subsequences using dynamic programming

func distinctSubsequences(sequence, word string) {
// Get the length of sequence
var n int = len(sequence)
// Get the length of word
var m int = len(word)
var dp = make([][] int, n + 1)
for i:= 0; i < n + 1;i++ {
dp[i] = make([]int,m+1)
}
// Set initial value of first column
for i := 0 ; i <= n ; i++ {
dp[i] = 1
}
for i := 0 ; i < n ; i++ {
for j := 0 ; j < m ; j++ {
if sequence[i] == word[j] {
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
} else {
dp[i + 1][j + 1] = dp[i][j + 1]
}
}
}
// Display given data
fmt.Print("\n Sequence : ", sequence)
fmt.Print("\n Word : ", word)
// Display calculated result
fmt.Print("\n Result : ", dp[n][m])
}
func main() {

var sequence string = "initcometipe"
var word string = "ice"
/*
sequence : initcometipe
word     : ice
------------------
initcometipe
-   -  -        ➀ [ice]

initcometipe
-   -      -    ➁ [ice]
initcometipe
- -  -        ➂ [ice]

initcometipe
- -      -    ➃ [ice]
-------------------------------
4 possible sequence
*/
distinctSubsequences(sequence, word)
}``````

#### Output

`````` Sequence : initcometipe
Word : ice
Result : 4``````
``````<?php
// Php program for
// Distinct subsequences using dynamic programming
class Subsequence
{
public	function distinctSubsequences(\$sequence, \$word)
{
// Get the length of sequence
\$n = strlen(\$sequence);
// Get the length of word
\$m = strlen(\$word);
\$dp = array_fill(0, \$n + 1, array_fill(0, \$m + 1, 0));
// Set initial value of first column
for (\$i = 0; \$i <= \$n; ++\$i)
{
\$dp[\$i] = 1;
}
for (\$i = 0; \$i < \$n; ++\$i)
{
for (\$j = 0; \$j < \$m; ++\$j)
{
if (\$sequence[\$i] == \$word[\$j])
{
// Change value when sequence contains word element
\$dp[\$i + 1][\$j + 1] = \$dp[\$i][\$j] + \$dp[\$i][\$j + 1];
}
else
{
\$dp[\$i + 1][\$j + 1] = \$dp[\$i][\$j + 1];
}
}
}
// Display given data
echo("\n Sequence : ".\$sequence);
echo("\n Word : ".\$word);
// Display calculated result
echo("\n Result : ".\$dp[\$n][\$m]);
}
}

function main()
{
\$sequence = "initcometipe";
\$word = "ice";
/*
sequence : initcometipe
word     : ice
------------------
initcometipe
-   -  -        ➀ [ice]

initcometipe
-   -      -    ➁ [ice]
initcometipe
- -  -        ➂ [ice]

initcometipe
- -      -    ➃ [ice]
-------------------------------
4 possible sequence
*/
}
main();``````

#### Output

`````` Sequence : initcometipe
Word : ice
Result : 4``````
``````// Node JS program for
// Distinct subsequences using dynamic programming
class Subsequence
{
distinctSubsequences(sequence, word)
{
// Get the length of sequence
var n = sequence.length;
// Get the length of word
var m = word.length;
var dp = Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
// Set initial value of first column
for (var i = 0; i <= n; ++i)
{
dp[i] = 1;
}
for (var i = 0; i < n; ++i)
{
for (var j = 0; j < m; ++j)
{
if (sequence.charAt(i) == word.charAt(j))
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
}
}
// Display given data
process.stdout.write("\n Sequence : " + sequence);
process.stdout.write("\n Word : " + word);
// Display calculated result
process.stdout.write("\n Result : " + dp[n][m]);
}
}

function main()
{
var sequence = "initcometipe";
var word = "ice";
/*
sequence : initcometipe
word     : ice
------------------
initcometipe
-   -  -        ➀ [ice]

initcometipe
-   -      -    ➁ [ice]
initcometipe
- -  -        ➂ [ice]

initcometipe
- -      -    ➃ [ice]
-------------------------------
4 possible sequence
*/
}
main();``````

#### Output

`````` Sequence : initcometipe
Word : ice
Result : 4``````
``````#  Python 3 program for
#  Distinct subsequences using dynamic programming
class Subsequence :
def distinctSubsequences(self, sequence, word) :
#  Get the length of sequence
n = len(sequence)
#  Get the length of word
m = len(word)
dp = [ * (m + 1) for _ in range(n + 1) ]
i = 0
#  Set initial value of first column
while (i <= n) :
dp[i] = 1
i += 1

i = 0
while (i < n) :
j = 0
while (j < m) :
if (sequence[i] == word[j]) :
#  Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
else :
dp[i + 1][j + 1] = dp[i][j + 1]

j += 1

i += 1

#  Display given data
print("\n Sequence : ", sequence, end = "")
print("\n Word : ", word, end = "")
#  Display calculated result
print("\n Result : ", dp[n][m], end = "")

def main() :
sequence = "initcometipe"
word = "ice"
#    sequence : initcometipe
#    word     : ice
#    ------------------
#        initcometipe
#        -   -  -        ➀ [ice]
#        initcometipe
#        -   -      -    ➁ [ice]
#        initcometipe
#          - -  -        ➂ [ice]
#        initcometipe
#          - -      -    ➃ [ice]
#    -------------------------------
#    4 possible sequence

if __name__ == "__main__": main()``````

#### Output

`````` Sequence :  initcometipe
Word :  ice
Result :  4``````
``````#  Ruby program for
#  Distinct subsequences using dynamic programming
class Subsequence
def distinctSubsequences(sequence, word)
#  Get the length of sequence
n = sequence.length
#  Get the length of word
m = word.length
dp = Array.new(n + 1) {Array.new(m + 1) {0}}
i = 0
#  Set initial value of first column
while (i <= n)
dp[i] = 1
i += 1
end

i = 0
while (i < n)
j = 0
while (j < m)
if (sequence[i] == word[j])
#  Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
else

dp[i + 1][j + 1] = dp[i][j + 1]
end

j += 1
end

i += 1
end

#  Display given data
print("\n Sequence : ", sequence)
print("\n Word : ", word)
#  Display calculated result
print("\n Result : ", dp[n][m])
end

end

def main()
sequence = "initcometipe"
word = "ice"
#    sequence : initcometipe
#    word     : ice
#    ------------------
#        initcometipe
#        -   -  -        ➀ [ice]
#        initcometipe
#        -   -      -    ➁ [ice]
#        initcometipe
#          - -  -        ➂ [ice]
#        initcometipe
#          - -      -    ➃ [ice]
#    -------------------------------
#    4 possible sequence
end

main()``````

#### Output

`````` Sequence : initcometipe
Word : ice
Result : 4``````
``````import scala.collection.mutable._;
// Scala program for
// Distinct subsequences using dynamic programming
class Subsequence()
{
def distinctSubsequences(sequence: String, word: String): Unit = {
// Get the length of sequence
var n: Int = sequence.length();
// Get the length of word
var m: Int = word.length();
var dp: Array[Array[Int]] = Array.fill[Int](n + 1, m + 1)(0);
var i: Int = 0;
// Set initial value of first column
while (i <= n)
{
dp(i)(0) = 1;
i += 1;
}
i = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (sequence.charAt(i) == word.charAt(j))
{
// Change value when sequence contains word element
dp(i + 1)(j + 1) = dp(i)(j) + dp(i)(j + 1);
}
else
{
dp(i + 1)(j + 1) = dp(i)(j + 1);
}
j += 1;
}
i += 1;
}
// Display given data
print("\n Sequence : " + sequence);
print("\n Word : " + word);
// Display calculated result
print("\n Result : " + dp(n)(m));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subsequence = new Subsequence();
var sequence: String = "initcometipe";
var word: String = "ice";
/*
sequence : initcometipe
word     : ice
------------------
initcometipe
-   -  -        ➀ [ice]

initcometipe
-   -      -    ➁ [ice]
initcometipe
- -  -        ➂ [ice]

initcometipe
- -      -    ➃ [ice]
-------------------------------
4 possible sequence
*/
}
}``````

#### Output

`````` Sequence : initcometipe
Word : ice
Result : 4``````
``````import Foundation;
// Swift 4 program for
// Distinct subsequences using dynamic programming
class Subsequence
{
func distinctSubsequences(_ s: String, _ w: String)
{
let sequence = Array(s);
let word = Array(w);
// Get the length of sequence
let n: Int = sequence.count;
// Get the length of word
let m: Int = word.count;
var dp: [[Int]] =
Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1);
var i: Int = 0;
// Set initial value of first column
while (i <= n)
{
dp[i] = 1;
i += 1;
}
i = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (sequence[i] == word[j])
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
j += 1;
}
i += 1;
}
// Display given data
print("\n Sequence : ", s, terminator: "");
print("\n Word : ", w, terminator: "");
// Display calculated result
print("\n Result : ", dp[n][m], terminator: "");
}
}
func main()
{
let sequence: String = "initcometipe";
let word: String = "ice";
/*
sequence : initcometipe
word     : ice
------------------
initcometipe
-   -  -        ➀ [ice]

initcometipe
-   -      -    ➁ [ice]
initcometipe
- -  -        ➂ [ice]

initcometipe
- -      -    ➃ [ice]
-------------------------------
4 possible sequence
*/
}
main();``````

#### Output

`````` Sequence :  initcometipe
Word :  ice
Result :  4``````
``````// Kotlin program for
// Distinct subsequences using dynamic programming
class Subsequence
{
fun distinctSubsequences(sequence: String, word: String): Unit
{
// Get the length of sequence
val n: Int = sequence.length;
// Get the length of word
val m: Int = word.length;
var dp: Array < Array < Int >> = Array(n + 1)
{
Array(m + 1)
{
0
}
};
var i: Int = 0;
// Set initial value of first column
while (i <= n)
{
dp[i] = 1;
i += 1;
}
i = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (sequence.get(i) == word.get(j))
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
j += 1;
}
i += 1;
}
// Display given data
print("\n Sequence : " + sequence);
print("\n Word : " + word);
// Display calculated result
print("\n Result : " + dp[n][m]);
}
}
fun main(args: Array < String > ): Unit
{
val sequence: String = "initcometipe";
val word: String = "ice";
/*
sequence : initcometipe
word     : ice
------------------
initcometipe
-   -  -        ➀ [ice]

initcometipe
-   -      -    ➁ [ice]
initcometipe
- -  -        ➂ [ice]

initcometipe
- -      -    ➃ [ice]
-------------------------------
4 possible sequence
*/
}``````

#### Output

`````` Sequence : initcometipe
Word : ice
Result : 4``````

## Output Explanation

Let's consider the example input:

``````Sequence: initcometipe
Word: ice
``````

The dynamic programming algorithm will construct a 2D array `dp` and calculate the number of distinct subsequences. The array `dp` will look as follows:

``````    i n i t c o m e t i p e
------------------------
i | 1 1 1 1 1 1 1 1 1 1 1
c | 0 0 0 0 1 1 1 1 1 1 1
e | 0 0 0 0 0 0 1 1 2 2 2
``````

The value in `dp` (the last element of the array) represents the number of distinct subsequences of the entire sequence that match the entire word. In this case, the value is 2, indicating that there are two distinct subsequences of "initcometipe" that match the word "ice".

## Time Complexity

The time complexity of this dynamic programming algorithm is O(n*m), where n is the length of the sequence and m is the length of the word. This is because we iterate over each character in the sequence and word exactly once, and the operations inside the loops take constant time.

## Finally

In this article, we discussed the problem of finding the number of distinct subsequences in a given sequence that match a given word using dynamic programming. We explained the approach, presented a step-by-step algorithm, provided pseudocode, and explained the output. Additionally, we analyzed the time complexity of the algorithm. By understanding this concept, you can efficiently solve similar problems that involve counting distinct subsequences.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.