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:
- Initialize the first column of
dpwith 1, as there is only one way to form an empty word from any prefix of the sequence. - 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]. - 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 asword[j]. - If
sequence[i]is equal toword[j], it means we can consider the current charactersequence[i]as part of the subsequence that matchesword[j]. In this case, we updatedp[i+1][j+1]as the sum of two values:dp[i][j](the number of distinct subsequences without considering the current character) anddp[i][j+1](the number of distinct subsequences considering the current character). - If
sequence[i]is not equal toword[j], it means we cannot consider the current charactersequence[i]as part of the subsequence that matchesword[j]. In this case, we updatedp[i+1][j+1]as the same value asdp[i][j+1](the number of distinct subsequences considering the current character). - 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[0][0] = 1 and dp[i][0] = 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][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
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][0] = 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)
{
Subsequence task = new Subsequence();
String sequence = "initcometipe";
String word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}
}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][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
cout << "\n Sequence : " << sequence;
cout << "\n Word : " << word;
// Display calculated result
cout << "\n Result : " << dp[n][m];
}
};
int main()
{
Subsequence *task = new Subsequence();
string sequence = "initcometipe";
string word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task->distinctSubsequences(sequence, word);
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)
{
Subsequence task = new Subsequence();
String sequence = "initcometipe";
String word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}
}Output
Sequence : initcometipe
Word : ice
Result : 4package 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][0] = 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][0] = 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()
{
$task = new Subsequence();
$sequence = "initcometipe";
$word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
$task->distinctSubsequences($sequence, $word);
}
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][0] = 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 task = new Subsequence();
var sequence = "initcometipe";
var word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}
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 = [[0] * (m + 1) for _ in range(n + 1) ]
i = 0
# Set initial value of first column
while (i <= n) :
dp[i][0] = 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() :
task = Subsequence()
sequence = "initcometipe"
word = "ice"
# sequence : initcometipe
# word : ice
# ------------------
# initcometipe
# - - - ➀ [ice]
# initcometipe
# - - - ➁ [ice]
# initcometipe
# - - - ➂ [ice]
# initcometipe
# - - - ➃ [ice]
# -------------------------------
# 4 possible sequence
task.distinctSubsequences(sequence, word)
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][0] = 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()
task = Subsequence.new()
sequence = "initcometipe"
word = "ice"
# sequence : initcometipe
# word : ice
# ------------------
# initcometipe
# - - - ➀ [ice]
# initcometipe
# - - - ➁ [ice]
# initcometipe
# - - - ➂ [ice]
# initcometipe
# - - - ➃ [ice]
# -------------------------------
# 4 possible sequence
task.distinctSubsequences(sequence, word)
end
main()Output
Sequence : initcometipe
Word : ice
Result : 4import 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
*/
task.distinctSubsequences(sequence, word);
}
}Output
Sequence : initcometipe
Word : ice
Result : 4import 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][0] = 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 task: Subsequence = Subsequence();
let sequence: String = "initcometipe";
let word: String = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}
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][0] = 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 task: Subsequence = Subsequence();
val sequence: String = "initcometipe";
val word: String = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}Output
Sequence : initcometipe
Word : ice
Result : 4Output 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[3][3] (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.
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.
New Comment