Skip to main content

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[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 : 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][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 : 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
		*/
		task.distinctSubsequences(sequence, word);
	}
}

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][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 : 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[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.





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.

New Comment