Skip to main content

Longest common substring using dynamic programming

This article discusses the implementation of finding the longest common substring between two strings using dynamic programming. We will explore the problem statement, provide a pseudocode algorithm with explanations, and analyze the resultant output with the time complexity of the code.

Problem Statement

The problem is to find the longest common substring between two given strings. A substring is a contiguous sequence of characters within a string. For example, in the strings "xycmitimesnxycode" and "xycstimesce," the longest common substring is "times," which appears in both strings.

Pseudocode Algorithm

To solve this problem efficiently, we can use dynamic programming. The following pseudocode algorithm outlines the steps involved: 

function longestCommonSubstring(str1, str2):
	n = length of str1
	m = length of str2

	if n <= 0 or m <= 0:
		return

	dp = 2D array of size (n+1) x (m+1)
	count = 0

	for i from 0 to n:
		for j from 0 to m:
			if i == 0 or j == 0:
				dp[i][j] = 0
			else if str1[i-1] == str2[j-1]:
				dp[i][j] = dp[i-1][j-1] + 1
				count = max(count, dp[i][j])
			else:
				dp[i][j] = 0

	print "Given: " + str1 + " " + str2
	print "Result: " + count

The algorithm uses a two-dimensional array, dp, to store the lengths of common substrings. The variable count keeps track of the maximum length encountered so far. The algorithm iterates over each character in both strings, comparing them and updating the dp array accordingly. Finally, it prints the given strings and the length of the longest common substring.

Code Solution

/*
    C program for
    Longest common substring using dynamic programming
*/
#include <stdio.h>
#include <string.h>

int maxValue(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	return b;
}
void longestCommonSubstring(char *str1, char *str2)
{
    // Get the length of given string
	int n = strlen(str1);
	int m = strlen(str2);
	if (n <= 0 || m <= 2)
	{
		return;
	}
	int dp[n + 1][m + 1];
	int count = 0;
	// Execute loop through by size of str1
	for (int i = 0; i <= n; ++i)
	{
		// Execute loop through by size of str2
		for (int j = 0; j <= m; ++j)
		{
			if (i == 0 || j == 0)
			{
				// Set default value when i and j is zero
				dp[i][j] = 0;
			}
			else if (str1[i - 1] == str2[j - 1])
			{
				// When str1[i-1] and str2[j - 1] are same
				// Then update dp[i][j] value 
				dp[i][j] = dp[i - 1][j - 1] + 1;
				// Get max value of given parameters
				count = maxValue(count, dp[i][j]);
			}
			else
			{
				// set zero
				dp[i][j] = 0;
			}
		}
	}
	// Display result
	printf(" Given  : %s %s", str1, str2);
	printf("\n Result : %d \n", count);
}
int main(int argc, char
	const *argv[])
{
	// Test
	// times
	longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
	// icd
	longestCommonSubstring("abxicde", "xyzavbicdn");
	return 0;
}

Output

 Given  : xycmitimesnxycode xycstimesce
 Result : 5
 Given  : abxicde xyzavbicdn
 Result : 3
/*
    Java program for
    Longest common substring using dynamic programming
*/
public class CommonSubstring
{
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public void longestCommonSubstring(String str1, String str2)
	{
		// Get the length of given string
		int n = str1.length();
		int m = str2.length();
		if (n <= 0 || m <= 2)
		{
			return;
		}
		// Use to collect common substring result
		int[][] dp = new int[n + 1][m + 1];
		int count = 0;
		// Execute loop through by size of str1
		for (int i = 0; i <= n; ++i)
		{
			// Execute loop through by size of str2
			for (int j = 0; j <= m; ++j)
			{
				if (i == 0 || j == 0)
				{
					// Set default value when i and j is zero
					dp[i][j] = 0;
				}
				else if (str1.charAt(i - 1) == str2.charAt(j - 1))
				{
					// When str1[i-1] and str2[j - 1] are same
					// Then update dp[i][j] value 
					dp[i][j] = dp[i - 1][j - 1] + 1;
					// Get max value of given parameters
					count = maxValue(count, dp[i][j]);
				}
				else
				{
					// set zero
					dp[i][j] = 0;
				}
			}
		}
		// Display result
		System.out.print(" Given : " + str1 + " " + str2);
		System.out.print("\n Result : " + count + " \n");
	}
	public static void main(String[] args)
	{
		CommonSubstring task = new CommonSubstring();
      	// str1 = xycmitimesnxycode str2 = xycstimesce
		// times  
      	// Result : 5
		task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
      	// str1 = abxicde str2 = xyzavbicdn
		// icd  
      	// Result : 3
		task.longestCommonSubstring("abxicde", "xyzavbicdn");
	}
}

Output

 Given : xycmitimesnxycode xycstimesce
 Result : 5
 Given : abxicde xyzavbicdn
 Result : 3
// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
    C++ program for
    Longest common substring using dynamic programming
*/
class CommonSubstring
{
	public: int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	void longestCommonSubstring(string str1, string str2)
	{
		// Get the length of given string
		int n = str1.length();
		int m = str2.length();
		if (n <= 0 || m <= 2)
		{
			return;
		}
		// Use to collect common substring result
		int dp[n + 1][m + 1];
		int count = 0;
		// Execute loop through by size of str1
		for (int i = 0; i <= n; ++i)
		{
			// Execute loop through by size of str2
			for (int j = 0; j <= m; ++j)
			{
				if (i == 0 || j == 0)
				{
					// Set default value when i and j is zero
					dp[i][j] = 0;
				}
				else if (str1[i - 1] == str2[j - 1])
				{
					// When str1[i-1] and str2[j - 1] are same
					// Then update dp[i][j] value 
					dp[i][j] = dp[i - 1][j - 1] + 1;
					// Get max value of given parameters
					count = this->maxValue(count, dp[i][j]);
				}
				else
				{
					// set zero
					dp[i][j] = 0;
				}
			}
		}
		// Display result
		cout << " Given : " << str1 << " " << str2;
		cout << "\n Result : " << count << " \n";
	}
};
int main()
{
	CommonSubstring *task = new CommonSubstring();
	// str1 = xycmitimesnxycode str2 = xycstimesce
	// times  
	// Result : 5
	task->longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
	// str1 = abxicde str2 = xyzavbicdn
	// icd  
	// Result : 3
	task->longestCommonSubstring("abxicde", "xyzavbicdn");
	return 0;
}

Output

 Given : xycmitimesnxycode xycstimesce
 Result : 5
 Given : abxicde xyzavbicdn
 Result : 3
// Include namespace system
using System;
/*
    Csharp program for
    Longest common substring using dynamic programming
*/
public class CommonSubstring
{
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public void longestCommonSubstring(String str1, String str2)
	{
		// Get the length of given string
		int n = str1.Length;
		int m = str2.Length;
		if (n <= 0 || m <= 2)
		{
			return;
		}
		// Use to collect common substring result
		int[,] dp = new int[n + 1,m + 1];
		int count = 0;
		// Execute loop through by size of str1
		for (int i = 0; i <= n; ++i)
		{
			// Execute loop through by size of str2
			for (int j = 0; j <= m; ++j)
			{
				if (i == 0 || j == 0)
				{
					// Set default value when i and j is zero
					dp[i,j] = 0;
				}
				else if (str1[i - 1] == str2[j - 1])
				{
					// When str1[i-1] and str2[j - 1] are same
					// Then update dp[i,j] value 
					dp[i,j] = dp[i - 1,j - 1] + 1;
					// Get max value of given parameters
					count = this.maxValue(count, dp[i,j]);
				}
				else
				{
					// set zero
					dp[i,j] = 0;
				}
			}
		}
		// Display result
		Console.Write(" Given : " + str1 + " " + str2);
		Console.Write("\n Result : " + count + " \n");
	}
	public static void Main(String[] args)
	{
		CommonSubstring task = new CommonSubstring();
		// str1 = xycmitimesnxycode str2 = xycstimesce
		// times  
		// Result : 5
		task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
		// str1 = abxicde str2 = xyzavbicdn
		// icd  
		// Result : 3
		task.longestCommonSubstring("abxicde", "xyzavbicdn");
	}
}

Output

 Given : xycmitimesnxycode xycstimesce
 Result : 5
 Given : abxicde xyzavbicdn
 Result : 3
package main

import "fmt"
/*
    Go program for
    Longest common substring using dynamic programming
*/

func maxValue(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func longestCommonSubstring(str1, str2 string) {
	// Get the length of given string
	var n int = len(str1)
	var m int = len(str2)
	if n <= 0 || m <= 2 {
		return
	}
	// Use to collect common substring result
	var dp = make([][]int,n+1)

	for i:=0 ; i <= n; i++ {
		dp[i] = make([]int,m+1)
	}
	var count int = 0
	// Execute loop through by size of str1
	for i := 0 ; i <= n ; i++ {
		// Execute loop through by size of str2
		for j := 0 ; j <= m ; j++ {
			if i == 0 || j == 0 {
				// Set default value when i and j is zero
				dp[i][j] = 0
			} else if str1[i - 1] == str2[j - 1] {
				// When str1[i-1] and str2[j - 1] are same
				// Then update dp[i][j] value 
				dp[i][j] = dp[i - 1][j - 1] + 1
				// Get max value of given parameters
				count = maxValue(count, dp[i][j])
			} else {
				// set zero
				dp[i][j] = 0
			}
		}
	}
	// Display result
	fmt.Print(" Given : ", str1, " ", str2)
	fmt.Print("\n Result : ", count, " \n")
}
func main() {
	
	// str1 = xycmitimesnxycode str2 = xycstimesce
	// times  
	// Result : 5
	longestCommonSubstring("xycmitimesnxycode", "xycstimesce")
	// str1 = abxicde str2 = xyzavbicdn
	// icd  
	// Result : 3
	longestCommonSubstring("abxicde", "xyzavbicdn")
}

Output

 Given : xycmitimesnxycode xycstimesce
 Result : 5 
 Given : abxicde xyzavbicdn
 Result : 3
<?php
/*
    Php program for
    Longest common substring using dynamic programming
*/
class CommonSubstring
{
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	public	function longestCommonSubstring($str1, $str2)
	{
		// Get the length of given string
		$n = strlen($str1);
		$m = strlen($str2);
		if ($n <= 0 || $m <= 2)
		{
			return;
		}
		// Use to collect common substring result
		$dp = array_fill(0, $n + 1, array_fill(0, $m + 1, 0));
		$count = 0;
		// Execute loop through by size of str1
		for ($i = 0; $i <= $n; ++$i)
		{
			// Execute loop through by size of str2
			for ($j = 0; $j <= $m; ++$j)
			{
				if ($i == 0 || $j == 0)
				{
					// Set default value when i and j is zero
					$dp[$i][$j] = 0;
				}
				else if ($str1[$i - 1] == $str2[$j - 1])
				{
					// When str1[i-1] and str2[j - 1] are same
					// Then update dp[i][j] value 
					$dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
					// Get max value of given parameters
					$count = $this->maxValue($count, $dp[$i][$j]);
				}
				else
				{
					// set zero
					$dp[$i][$j] = 0;
				}
			}
		}
		// Display result
		echo(" Given : ".$str1.
			" ".$str2);
		echo("\n Result : ".$count.
			" \n");
	}
}

function main()
{
	$task = new CommonSubstring();
	// str1 = xycmitimesnxycode str2 = xycstimesce
	// times  
	// Result : 5
	$task->longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
	// str1 = abxicde str2 = xyzavbicdn
	// icd  
	// Result : 3
	$task->longestCommonSubstring("abxicde", "xyzavbicdn");
}
main();

Output

 Given : xycmitimesnxycode xycstimesce
 Result : 5
 Given : abxicde xyzavbicdn
 Result : 3
/*
    Node JS program for
    Longest common substring using dynamic programming
*/
class CommonSubstring
{
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	longestCommonSubstring(str1, str2)
	{
		// Get the length of given string
		var n = str1.length;
		var m = str2.length;
		if (n <= 0 || m <= 2)
		{
			return;
		}
		// Use to collect common substring result
		var dp = Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
		var count = 0;
		// Execute loop through by size of str1
		for (var i = 0; i <= n; ++i)
		{
			// Execute loop through by size of str2
			for (var j = 0; j <= m; ++j)
			{
				if (i == 0 || j == 0)
				{
					// Set default value when i and j is zero
					dp[i][j] = 0;
				}
				else if (str1.charAt(i - 1) == str2.charAt(j - 1))
				{
					// When str1[i-1] and str2[j - 1] are same
					// Then update dp[i][j] value 
					dp[i][j] = dp[i - 1][j - 1] + 1;
					// Get max value of given parameters
					count = this.maxValue(count, dp[i][j]);
				}
				else
				{
					// set zero
					dp[i][j] = 0;
				}
			}
		}
		// Display result
		process.stdout.write(" Given : " + str1 + " " + str2);
		process.stdout.write("\n Result : " + count + " \n");
	}
}

function main()
{
	var task = new CommonSubstring();
	// str1 = xycmitimesnxycode str2 = xycstimesce
	// times  
	// Result : 5
	task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
	// str1 = abxicde str2 = xyzavbicdn
	// icd  
	// Result : 3
	task.longestCommonSubstring("abxicde", "xyzavbicdn");
}
main();

Output

 Given : xycmitimesnxycode xycstimesce
 Result : 5
 Given : abxicde xyzavbicdn
 Result : 3
#    Python 3 program for
#    Longest common substring using dynamic programming
class CommonSubstring :
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		
		return b
	
	def longestCommonSubstring(self, str1, str2) :
		#  Get the length of given string
		n = len(str1)
		m = len(str2)
		if (n <= 0 or m <= 2) :
			return
		
		#  Use to collect common substring result
		dp = [[0] * (m + 1) for _ in range(n + 1) ]
		count = 0
		i = 0
		#  Execute loop through by size of str1
		while (i <= n) :
			j = 0
			#  Execute loop through by size of str2
			while (j <= m) :
				if (i == 0 or j == 0) :
					#  Set default value when i and j is zero
					dp[i][j] = 0
				elif (str1[i - 1] == str2[j - 1]) :
					#  When str1[i-1] and str2[j - 1] are same
					#  Then update dp[i][j] value 
					dp[i][j] = dp[i - 1][j - 1] + 1
					#  Get max value of given parameters
					count = self.maxValue(count, dp[i][j])
				else :
					#  set zero
					dp[i][j] = 0
				
				j += 1
			
			i += 1
		
		#  Display result
		print(" Given : ", str1 ," ", str2, end = "")
		print("\n Result : ", count ," ")
	

def main() :
	task = CommonSubstring()
	#  str1 = xycmitimesnxycode str2 = xycstimesce
	#  times  
	#  Result : 5
	task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce")
	#  str1 = abxicde str2 = xyzavbicdn
	#  icd  
	#  Result : 3
	task.longestCommonSubstring("abxicde", "xyzavbicdn")

if __name__ == "__main__": main()

Output

 Given :  xycmitimesnxycode   xycstimesce
 Result :  5
 Given :  abxicde   xyzavbicdn
 Result :  3
#    Ruby program for
#    Longest common substring using dynamic programming
class CommonSubstring 
	def maxValue(a, b) 
		if (a > b) 
			return a
		end

		return b
	end

	def longestCommonSubstring(str1, str2) 
		#  Get the length of given string
		n = str1.length
		m = str2.length
		if (n <= 0 || m <= 2) 
			return
		end

		#  Use to collect common substring result
		dp = Array.new(n + 1) {Array.new(m + 1) {0}}
		count = 0
		i = 0
		#  Execute loop through by size of str1
		while (i <= n) 
			j = 0
			#  Execute loop through by size of str2
			while (j <= m) 
				if (i == 0 || j == 0) 
					#  Set default value when i and j is zero
					dp[i][j] = 0
				elsif (str1[i - 1] == str2[j - 1]) 
					#  When str1[i-1] and str2[j - 1] are same
					#  Then update dp[i][j] value 
					dp[i][j] = dp[i - 1][j - 1] + 1
					#  Get max value of given parameters
					count = self.maxValue(count, dp[i][j])
				else
 
					#  set zero
					dp[i][j] = 0
				end

				j += 1
			end

			i += 1
		end

		#  Display result
		print(" Given : ", str1 ," ", str2)
		print("\n Result : ", count ," \n")
	end

end

def main() 
	task = CommonSubstring.new()
	#  str1 = xycmitimesnxycode str2 = xycstimesce
	#  times  
	#  Result : 5
	task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce")
	#  str1 = abxicde str2 = xyzavbicdn
	#  icd  
	#  Result : 3
	task.longestCommonSubstring("abxicde", "xyzavbicdn")
end

main()

Output

 Given : xycmitimesnxycode xycstimesce
 Result : 5 
 Given : abxicde xyzavbicdn
 Result : 3 

/*
    Scala program for
    Longest common substring using dynamic programming
*/
class CommonSubstring()
{
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	def longestCommonSubstring(str1: String, str2: String): Unit = {
		// Get the length of given string
		var n: Int = str1.length();
		var m: Int = str2.length();
		if (n <= 0 || m <= 2)
		{
			return;
		}
		// Use to collect common substring result
		var dp: Array[Array[Int]] = Array.fill[Int](n + 1, m + 1)(0);
		var count: Int = 0;
		var i: Int = 0;
		// Execute loop through by size of str1
		while (i <= n)
		{
			var j: Int = 0;
			// Execute loop through by size of str2
			while (j <= m)
			{
				if (i == 0 || j == 0)
				{
					// Set default value when i and j is zero
					dp(i)(j) = 0;
				}
				else if (str1.charAt(i - 1) == str2.charAt(j - 1))
				{
					// When str1[i-1] and str2[j - 1] are same
					// Then update dp[i][j] value 
					dp(i)(j) = dp(i - 1)(j - 1) + 1;
					// Get max value of given parameters
					count = maxValue(count, dp(i)(j));
				}
				else
				{
					// set zero
					dp(i)(j) = 0;
				}
				j += 1;
			}
			i += 1;
		}
		// Display result
		print(" Given : " + str1 + " " + str2);
		print("\n Result : " + count + " \n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: CommonSubstring = new CommonSubstring();
		// str1 = xycmitimesnxycode str2 = xycstimesce
		// times  
		// Result : 5
		task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
		// str1 = abxicde str2 = xyzavbicdn
		// icd  
		// Result : 3
		task.longestCommonSubstring("abxicde", "xyzavbicdn");
	}
}

Output

 Given : xycmitimesnxycode xycstimesce
 Result : 5
 Given : abxicde xyzavbicdn
 Result : 3
import Foundation;
/*
    Swift 4 program for
    Longest common substring using dynamic programming
*/
class CommonSubstring
{
	func maxValue(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	func longestCommonSubstring(_ s1: String, _ s2: String)
	{
		// Get the length of given string
		let n: Int = s1.count;
		let m: Int = s2.count;
      	let str1 = Array(s1);
        let str2 = Array(s2);
		if (n <= 0 || m <= 2)
		{
			return;
		}
		// Use to collect common substring result
		var dp: [
			[Int]
		] = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1);
		var count: Int = 0;
		var i: Int = 0;
		// Execute loop through by size of str1
		while (i <= n)
		{
			var j: Int = 0;
			// Execute loop through by size of str2
			while (j <= m)
			{
				if (i == 0 || j == 0)
				{
					// Set default value when i and j is zero
					dp[i][j] = 0;
				}
				else if (str1[i - 1] == str2[j - 1])
				{
					// When str1[i-1] and str2[j - 1] are same
					// Then update dp[i][j] value 
					dp[i][j] = dp[i - 1][j - 1] + 1;
					// Get max value of given parameters
					count = self.maxValue(count, dp[i][j]);
				}
				else
				{
					// set zero
					dp[i][j] = 0;
				}
				j += 1;
			}
			i += 1;
		}
		// Display result
		print(" Given : ", s1 ," ", s2, terminator: "");
		print("\n Result : ", count ," ");
	}
}
func main()
{
	let task: CommonSubstring = CommonSubstring();
	// str1 = xycmitimesnxycode str2 = xycstimesce
	// times  
	// Result : 5
	task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
	// str1 = abxicde str2 = xyzavbicdn
	// icd  
	// Result : 3
	task.longestCommonSubstring("abxicde", "xyzavbicdn");
}
main();

Output

 Given :  xycmitimesnxycode   xycstimesce
 Result :  5
 Given :  abxicde   xyzavbicdn
 Result :  3
/*
    Kotlin program for
    Longest common substring using dynamic programming
*/
class CommonSubstring
{
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	fun longestCommonSubstring(str1: String, str2: String): Unit
	{
		// Get the length of given string
		val n: Int = str1.length;
		val m: Int = str2.length;
		if (n <= 0 || m <= 2)
		{
			return;
		}
		// Use to collect common substring result
		var dp: Array < Array < Int >> = Array(n + 1)
		{
			Array(m + 1)
			{
				0
			}
		};
		var count: Int = 0;
		var i: Int = 0;
		// Execute loop through by size of str1
		while (i <= n)
		{
			var j: Int = 0;
			// Execute loop through by size of str2
			while (j <= m)
			{
				if (i == 0 || j == 0)
				{
					// Set default value when i and j is zero
					dp[i][j] = 0;
				}
				else if (str1.get(i - 1) == str2.get(j - 1))
				{
					// When str1[i-1] and str2[j - 1] are same
					// Then update dp[i][j] value 
					dp[i][j] = dp[i - 1][j - 1] + 1;
					// Get max value of given parameters
					count = this.maxValue(count, dp[i][j]);
				}
				else
				{
					// set zero
					dp[i][j] = 0;
				}
				j += 1;
			}
			i += 1;
		}
		// Display result
		print(" Given : " + str1 + " " + str2);
		print("\n Result : " + count + " \n");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: CommonSubstring = CommonSubstring();
	// str1 = xycmitimesnxycode str2 = xycstimesce
	// times  
	// Result : 5
	task.longestCommonSubstring("xycmitimesnxycode", "xycstimesce");
	// str1 = abxicde str2 = xyzavbicdn
	// icd  
	// Result : 3
	task.longestCommonSubstring("abxicde", "xyzavbicdn");
}

Output

 Given : xycmitimesnxycode xycstimesce
 Result : 5
 Given : abxicde xyzavbicdn
 Result : 3

Resultant Output Explanation

Let's analyze the output of the provided test cases: 

Given: xycmitimesnxycode xycstimesce
Result: 5

In the first test case, the longest common substring between "xycmitimesnxycode" and "xycstimesce" is "times." The length of this substring is 5, which is correctly displayed in the output. 

Given: abxicde xyzavbicdn
Result: 3

In the second test case, the longest common substring between "abxicde" and "xyzavbicdn" is "icd." The length of this substring is 3, which is correctly displayed in the output.

Time Complexity

The time complexity of the provided algorithm is O(n * m), where n and m are the lengths of the input strings. This is because the algorithm requires nested loops to compare each character of both strings and update the dp array. As a result, the algorithm's execution time grows linearly with the sizes of the input strings.

Last updated on by Kalkicode




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