Skip to main content

Shortest uncommon subsequence using dynamic programming

Here given code implementation process.

/*
    Java program for
    Shortest uncommon subsequence using dynamic programming
*/
public class Subsequence
{
	public int minValue(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	// Find the length of shortest uncommon subsequence which is exist
	// In str1 but not in str2.
	public void uncommonSubsequence(
    	String str1, 
     		String str2)
	{
		// Get the length
		int m = str1.length();
		int n = str2.length();
      	// Auxiliary space
		int[][] dp = new int[m + 1][n + 1];
		int result = 0;
		int max = Integer.MAX_VALUE;
		// Reduce size of max by length of longest substring
		if (n > m)
		{
			max -= n;
		}
		else
		{
			max -= m;
		}
		for (int i = 0; i <= m; i++)
		{
			dp[i][0] = 1;
		}
		for (int i = 0; i <= n; i++)
		{
			dp[0][i] = max;
		}
		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				int k = j - 1;
				while (k >= 0 && str2.charAt(k) != str1.charAt(i - 1))
				{
					k--;
				}
				if (k == -1)
				{
					dp[i][j] = 1;
				}
				else
				{
					dp[i][j] = minValue(dp[i - 1][j], dp[i - 1][k] + 1);
				}
			}
		}
		if (dp[m][n] != max)
		{
			result = dp[m][n];
		}
		// Display given strings
		System.out.println(" String A : " + str1);
		System.out.println(" String B : " + str2);
		// Display calculated result
		System.out.println(" " + result);
	}
	public static void main(String[] args)
	{
		Subsequence task = new Subsequence();
		String str1 = "aecb";
		String str2 = "bace";
		// Case A
		/*
		   Example 1

		   str1 = aecb
		   str2 = bace
		   ------------
		    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
            str1 but not str2
		    --------------------------------------------
		    Length of shortest subsequence is 2
		    Ans = 2
		*/
		task.uncommonSubsequence(str1, str2);
		// Case B
		str1 = "ABCCDBE";
		str2 = "ABCCDBE";
		/*
		   Example 2
		   
		   str1 = ABCCDBE
		   str2 = ABCCDBE
		   ------------
		   all subsequence str1 exist in str2
		*/
		task.uncommonSubsequence(str1, str2);
		// Case C
		str1 = "CCCCCB";
		str2 = "CCB";
		/*
		   Example 3
		   
		   str1 = CCCCCB
		   str2 = CCB
		   ------------
		   'CCC' Shortest subsequence which exist in str1 but not on str2.
		   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
		   but its length more than 3.
		   --------------------------------------------------------
		   Ans = 3
		*/
		task.uncommonSubsequence(str1, str2);
		// Case D
		str1 = "fbi";
		str2 = "ice";
		/*
		   Example 4
		   
		   str1 = fbi
		   str2 = ice
		   ------------
		    [f,b,fb,fbi]
		    Subsequences which is exist in str1 but not on str2.
		   --------------------------------------------------------
		   Ans = 1  [length of f or b]
		*/
		task.uncommonSubsequence(str1, str2);
	}
}

Output

 String A : aecb
 String B : bace
 2
 String A : ABCCDBE
 String B : ABCCDBE
 0
 String A : CCCCCB
 String B : CCB
 3
 String A : fbi
 String B : ice
 1
// Include header file
#include <iostream>
#include <string>
#include <limits.h>

using namespace std;
/*
    C++ program for
    Shortest uncommon subsequence using dynamic programming
*/
class Subsequence
{
	public: int minValue(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	// Find the length of shortest uncommon subsequence which is exist
	// In str1 but not in str2.
	void uncommonSubsequence(string str1, string str2)
	{
		// Get the length
		int m = str1.length();
		int n = str2.length();
		// Auxiliary space
		int dp[m + 1][n + 1];
		int result = 0;
		int max = INT_MAX;
		// Reduce size of max by length of longest substring
		if (n > m)
		{
			max -= n;
		}
		else
		{
			max -= m;
		}
		for (int i = 0; i <= m; i++)
		{
			dp[i][0] = 1;
		}
		for (int i = 0; i <= n; i++)
		{
			dp[0][i] = max;
		}
		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				int k = j - 1;
				while (k >= 0 && str2[k] != str1[i - 1])
				{
					k--;
				}
				if (k == -1)
				{
					dp[i][j] = 1;
				}
				else
				{
					dp[i][j] = this->minValue(dp[i - 1][j], dp[i - 1][k] + 1);
				}
			}
		}
		if (dp[m][n] != max)
		{
			result = dp[m][n];
		}
		// Display given strings
		cout << " String A : " << str1 << endl;
		cout << " String B : " << str2 << endl;
		// Display calculated result
		cout << " " << result << endl;
	}
};
int main()
{
	Subsequence *task = new Subsequence();
	string str1 = "aecb";
	string str2 = "bace";
	// Case A
	/*
	   Example 1
	   str1 = aecb
	   str2 = bace
	   ------------
	    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
	            str1 but not str2
	    --------------------------------------------
	    Length of shortest subsequence is 2
	    Ans = 2
	*/
	task->uncommonSubsequence(str1, str2);
	// Case B
	str1 = "ABCCDBE";
	str2 = "ABCCDBE";
	/*
	   Example 2
	   
	   str1 = ABCCDBE
	   str2 = ABCCDBE
	   ------------
	   all subsequence str1 exist in str2
	*/
	task->uncommonSubsequence(str1, str2);
	// Case C
	str1 = "CCCCCB";
	str2 = "CCB";
	/*
	   Example 3
	   
	   str1 = CCCCCB
	   str2 = CCB
	   ------------
	   'CCC' Shortest subsequence which exist in str1 but not on str2.
	   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
	   but its length more than 3.
	   --------------------------------------------------------
	   Ans = 3
	*/
	task->uncommonSubsequence(str1, str2);
	// Case D
	str1 = "fbi";
	str2 = "ice";
	/*
	   Example 4
	   
	   str1 = fbi
	   str2 = ice
	   ------------
	    [f,b,fb,fbi]
	    Subsequences which is exist in str1 but not on str2.
	   --------------------------------------------------------
	   Ans = 1  [length of f or b]
	*/
	task->uncommonSubsequence(str1, str2);
	return 0;
}

Output

 String A : aecb
 String B : bace
 2
 String A : ABCCDBE
 String B : ABCCDBE
 0
 String A : CCCCCB
 String B : CCB
 3
 String A : fbi
 String B : ice
 1
// Include namespace system
using System;
/*
    Csharp program for
    Shortest uncommon subsequence using dynamic programming
*/
public class Subsequence
{
	public int minValue(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	// Find the length of shortest uncommon subsequence which is exist
	// In str1 but not in str2.
	public void uncommonSubsequence(String str1, String str2)
	{
		// Get the length
		int m = str1.Length;
		int n = str2.Length;
		// Auxiliary space
		int[,] dp = new int[m + 1,n + 1];
		int result = 0;
		int max = int.MaxValue;
		// Reduce size of max by length of longest substring
		if (n > m)
		{
			max -= n;
		}
		else
		{
			max -= m;
		}
		for (int i = 0; i <= m; i++)
		{
			dp[i,0] = 1;
		}
		for (int i = 0; i <= n; i++)
		{
			dp[0,i] = max;
		}
		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				int k = j - 1;
				while (k >= 0 && str2[k] != str1[i - 1])
				{
					k--;
				}
				if (k == -1)
				{
					dp[i,j] = 1;
				}
				else
				{
					dp[i,j] = this.minValue(dp[i - 1,j], dp[i - 1,k] + 1);
				}
			}
		}
		if (dp[m,n] != max)
		{
			result = dp[m,n];
		}
		// Display given strings
		Console.WriteLine(" String A : " + str1);
		Console.WriteLine(" String B : " + str2);
		// Display calculated result
		Console.WriteLine(" " + result);
	}
	public static void Main(String[] args)
	{
		Subsequence task = new Subsequence();
		String str1 = "aecb";
		String str2 = "bace";
		// Case A
		/*
		   Example 1
		   str1 = aecb
		   str2 = bace
		   ------------
		    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
		            str1 but not str2
		    --------------------------------------------
		    Length of shortest subsequence is 2
		    Ans = 2
		*/
		task.uncommonSubsequence(str1, str2);
		// Case B
		str1 = "ABCCDBE";
		str2 = "ABCCDBE";
		/*
		   Example 2
		   
		   str1 = ABCCDBE
		   str2 = ABCCDBE
		   ------------
		   all subsequence str1 exist in str2
		*/
		task.uncommonSubsequence(str1, str2);
		// Case C
		str1 = "CCCCCB";
		str2 = "CCB";
		/*
		   Example 3
		   
		   str1 = CCCCCB
		   str2 = CCB
		   ------------
		   'CCC' Shortest subsequence which exist in str1 but not on str2.
		   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
		   but its length more than 3.
		   --------------------------------------------------------
		   Ans = 3
		*/
		task.uncommonSubsequence(str1, str2);
		// Case D
		str1 = "fbi";
		str2 = "ice";
		/*
		   Example 4
		   
		   str1 = fbi
		   str2 = ice
		   ------------
		    [f,b,fb,fbi]
		    Subsequences which is exist in str1 but not on str2.
		   --------------------------------------------------------
		   Ans = 1  [length of f or b]
		*/
		task.uncommonSubsequence(str1, str2);
	}
}

Output

 String A : aecb
 String B : bace
 2
 String A : ABCCDBE
 String B : ABCCDBE
 0
 String A : CCCCCB
 String B : CCB
 3
 String A : fbi
 String B : ice
 1
package main
import "math"
import "fmt"
/*
    Go program for
    Shortest uncommon subsequence using dynamic programming
*/

func minValue(a, b int) int {
	if a < b {
		return a
	}
	return b
}
// Find the length of shortest uncommon subsequence which is exist
// In str1 but not in str2.
func uncommonSubsequence(str1, str2 string) {
	// Get the length
	var m int = len(str1)
	var n int = len(str2)
	// Auxiliary space
	var dp = make([][] int, m + 1)
	for i:= 0;i < m + 1; i++ {
		dp[i] = make([]int ,n + 1)
	}
	var result int = 0
	var max int = math.MaxInt64
	// Reduce size of max by length of longest substring
	if n > m {
		max -= n
	} else {
		max -= m
	}
	for i := 0 ; i <= m ; i++ {
		dp[i][0] = 1
	}
	for i := 0 ; i <= n ; i++ {
		dp[0][i] = max
	}
	for i := 1 ; i <= m ; i++ {
		for j := 1 ; j <= n ; j++ {
			var k int = j - 1
			for (k >= 0 && str2[k] != str1[i - 1]) {
				k--
			}
			if k == -1 {
				dp[i][j] = 1
			} else {
				dp[i][j] = minValue(dp[i - 1][j], dp[i - 1][k] + 1)
			}
		}
	}
	if dp[m][n] != max {
		result = dp[m][n]
	}
	// Display given strings
	fmt.Println(" String A : ", str1)
	fmt.Println(" String B : ", str2)
	// Display calculated result
	fmt.Println(" ", result)
}
func main() {

	var str1 string = "aecb"
	var str2 string = "bace"
	// Case A
	/*
	   Example 1
	   str1 = aecb
	   str2 = bace
	   ------------
	    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
	            str1 but not str2
	    --------------------------------------------
	    Length of shortest subsequence is 2
	    Ans = 2
	*/
	uncommonSubsequence(str1, str2)
	// Case B
	str1 = "ABCCDBE"
	str2 = "ABCCDBE"
	/*
	   Example 2
	   
	   str1 = ABCCDBE
	   str2 = ABCCDBE
	   ------------
	   all subsequence str1 exist in str2
	*/
	uncommonSubsequence(str1, str2)
	// Case C
	str1 = "CCCCCB"
	str2 = "CCB"
	/*
	   Example 3
	   
	   str1 = CCCCCB
	   str2 = CCB
	   ------------
	   'CCC' Shortest subsequence which exist in str1 but not on str2.
	   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
	   but its length more than 3.
	   --------------------------------------------------------
	   Ans = 3
	*/
	uncommonSubsequence(str1, str2)
	// Case D
	str1 = "fbi"
	str2 = "ice"
	/*
	   Example 4
	   
	   str1 = fbi
	   str2 = ice
	   ------------
	    [f,b,fb,fbi]
	    Subsequences which is exist in str1 but not on str2.
	   --------------------------------------------------------
	   Ans = 1  [length of f or b]
	*/
	uncommonSubsequence(str1, str2)
}

Output

 String A :  aecb
 String B :  bace
  2
 String A :  ABCCDBE
 String B :  ABCCDBE
  0
 String A :  CCCCCB
 String B :  CCB
  3
 String A :  fbi
 String B :  ice
  1

<?php
/*
    Php program for
    Shortest uncommon subsequence using dynamic programming
*/
class Subsequence
{
	public	function minValue($a, $b)
	{
		if ($a < $b)
		{
			return $a;
		}
		return $b;
	}
	// Find the length of shortest uncommon subsequence which is exist
	// In str1 but not in str2.
	public	function uncommonSubsequence($str1, $str2)
	{
		// Get the length
		$m = strlen($str1);
		$n = strlen($str2);
		// Auxiliary space
		$dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
		$result = 0;
		$max = PHP_INT_MAX;
		// Reduce size of max by length of longest substring
		if ($n > $m)
		{
			$max -= $n;
		}
		else
		{
			$max -= $m;
		}
		for ($i = 0; $i <= $m; $i++)
		{
			$dp[$i][0] = 1;
		}
		for ($i = 0; $i <= $n; $i++)
		{
			$dp[0][$i] = $max;
		}
		for ($i = 1; $i <= $m; $i++)
		{
			for ($j = 1; $j <= $n; $j++)
			{
				$k = $j - 1;
				while ($k >= 0 && $str2[$k] != $str1[$i - 1])
				{
					$k--;
				}
				if ($k == -1)
				{
					$dp[$i][$j] = 1;
				}
				else
				{
					$dp[$i][$j] = $this->minValue($dp[$i - 1][$j], $dp[$i - 1][$k] + 1);
				}
			}
		}
		if ($dp[$m][$n] != $max)
		{
			$result = $dp[$m][$n];
		}
		// Display given strings
		echo(" String A : ".$str1.
			"\n");
		echo(" String B : ".$str2.
			"\n");
		// Display calculated result
		echo(" ".$result.
			"\n");
	}
}

function main()
{
	$task = new Subsequence();
	$str1 = "aecb";
	$str2 = "bace";
	// Case A
	/*
	   Example 1
	   str1 = aecb
	   str2 = bace
	   ------------
	    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
	            str1 but not str2
	    --------------------------------------------
	    Length of shortest subsequence is 2
	    Ans = 2
	*/
	$task->uncommonSubsequence($str1, $str2);
	// Case B
	$str1 = "ABCCDBE";
	$str2 = "ABCCDBE";
	/*
	   Example 2
	   
	   str1 = ABCCDBE
	   str2 = ABCCDBE
	   ------------
	   all subsequence str1 exist in str2
	*/
	$task->uncommonSubsequence($str1, $str2);
	// Case C
	$str1 = "CCCCCB";
	$str2 = "CCB";
	/*
	   Example 3
	   
	   str1 = CCCCCB
	   str2 = CCB
	   ------------
	   'CCC' Shortest subsequence which exist in str1 but not on str2.
	   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
	   but its length more than 3.
	   --------------------------------------------------------
	   Ans = 3
	*/
	$task->uncommonSubsequence($str1, $str2);
	// Case D
	$str1 = "fbi";
	$str2 = "ice";
	/*
	   Example 4
	   
	   str1 = fbi
	   str2 = ice
	   ------------
	    [f,b,fb,fbi]
	    Subsequences which is exist in str1 but not on str2.
	   --------------------------------------------------------
	   Ans = 1  [length of f or b]
	*/
	$task->uncommonSubsequence($str1, $str2);
}
main();

Output

 String A : aecb
 String B : bace
 2
 String A : ABCCDBE
 String B : ABCCDBE
 0
 String A : CCCCCB
 String B : CCB
 3
 String A : fbi
 String B : ice
 1
/*
    Node JS program for
    Shortest uncommon subsequence using dynamic programming
*/
class Subsequence
{
	minValue(a, b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	// Find the length of shortest uncommon subsequence which is exist
	// In str1 but not in str2.
	uncommonSubsequence(str1, str2)
	{
		// Get the length
		var m = str1.length;
		var n = str2.length;
		// Auxiliary space
		var dp = Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
		var result = 0;
		var max = Number.MAX_VALUE;
		// Reduce size of max by length of longest substring
		if (n > m)
		{
			max -= n;
		}
		else
		{
			max -= m;
		}
		for (var i = 0; i <= m; i++)
		{
			dp[i][0] = 1;
		}
		for (var i = 0; i <= n; i++)
		{
			dp[0][i] = max;
		}
		for (var i = 1; i <= m; i++)
		{
			for (var j = 1; j <= n; j++)
			{
				var k = j - 1;
				while (k >= 0 && str2.charAt(k) != str1.charAt(i - 1))
				{
					k--;
				}
				if (k == -1)
				{
					dp[i][j] = 1;
				}
				else
				{
					dp[i][j] = this.minValue(dp[i - 1][j], dp[i - 1][k] + 1);
				}
			}
		}
		if (dp[m][n] != max)
		{
			result = dp[m][n];
		}
		// Display given strings
		console.log(" String A : " + str1);
		console.log(" String B : " + str2);
		// Display calculated result
		console.log(" " + result);
	}
}

function main()
{
	var task = new Subsequence();
	var str1 = "aecb";
	var str2 = "bace";
	// Case A
	/*
	   Example 1
	   str1 = aecb
	   str2 = bace
	   ------------
	    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
	            str1 but not str2
	    --------------------------------------------
	    Length of shortest subsequence is 2
	    Ans = 2
	*/
	task.uncommonSubsequence(str1, str2);
	// Case B
	str1 = "ABCCDBE";
	str2 = "ABCCDBE";
	/*
	   Example 2
	   
	   str1 = ABCCDBE
	   str2 = ABCCDBE
	   ------------
	   all subsequence str1 exist in str2
	*/
	task.uncommonSubsequence(str1, str2);
	// Case C
	str1 = "CCCCCB";
	str2 = "CCB";
	/*
	   Example 3
	   
	   str1 = CCCCCB
	   str2 = CCB
	   ------------
	   'CCC' Shortest subsequence which exist in str1 but not on str2.
	   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
	   but its length more than 3.
	   --------------------------------------------------------
	   Ans = 3
	*/
	task.uncommonSubsequence(str1, str2);
	// Case D
	str1 = "fbi";
	str2 = "ice";
	/*
	   Example 4
	   
	   str1 = fbi
	   str2 = ice
	   ------------
	    [f,b,fb,fbi]
	    Subsequences which is exist in str1 but not on str2.
	   --------------------------------------------------------
	   Ans = 1  [length of f or b]
	*/
	task.uncommonSubsequence(str1, str2);
}
main();

Output

 String A : aecb
 String B : bace
 2
 String A : ABCCDBE
 String B : ABCCDBE
 0
 String A : CCCCCB
 String B : CCB
 3
 String A : fbi
 String B : ice
 1
import sys
#    Python 3 program for
#    Shortest uncommon subsequence using dynamic programming
class Subsequence :
	def minValue(self, a, b) :
		if (a < b) :
			return a
		
		return b
	
	#  Find the length of shortest uncommon subsequence which is exist
	#  In str1 but not in str2.
	def uncommonSubsequence(self, str1, str2) :
		#  Get the length
		m = len(str1)
		n = len(str2)
		#  Auxiliary space
		dp = [[0] * (n + 1) for _ in range(m + 1) ]
		result = 0
		max = sys.maxsize
		#  Reduce size of max by length of longest substring
		if (n > m) :
			max -= n
		else :
			max -= m
		
		i = 0
		while (i <= m) :
			dp[i][0] = 1
			i += 1
		
		i = 0
		while (i <= n) :
			dp[0][i] = max
			i += 1
		
		i = 1
		while (i <= m) :
			j = 1
			while (j <= n) :
				k = j - 1
				while (k >= 0 and str2[k] != str1[i - 1]) :
					k -= 1
				
				if (k == -1) :
					dp[i][j] = 1
				else :
					dp[i][j] = self.minValue(dp[i - 1][j], dp[i - 1][k] + 1)
				
				j += 1
			
			i += 1
		
		if (dp[m][n] != max) :
			result = dp[m][n]
		
		#  Display given strings
		print(" String A : ", str1)
		print(" String B : ", str2)
		#  Display calculated result
		print(" ", result)
	

def main() :
	task = Subsequence()
	str1 = "aecb"
	str2 = "bace"
	#  Case A
	#   Example 1
	#   str1 = aecb
	#   str2 = bace
	#   ------------
	#    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
	#            str1 but not str2
	#    --------------------------------------------
	#    Length of shortest subsequence is 2
	#    Ans = 2
	task.uncommonSubsequence(str1, str2)
	#  Case B
	str1 = "ABCCDBE"
	str2 = "ABCCDBE"
	#   Example 2
	#   str1 = ABCCDBE
	#   str2 = ABCCDBE
	#   ------------
	#   all subsequence str1 exist in str2
	task.uncommonSubsequence(str1, str2)
	#  Case C
	str1 = "CCCCCB"
	str2 = "CCB"
	#   Example 3
	#   str1 = CCCCCB
	#   str2 = CCB
	#   ------------
	#   'CCC' Shortest subsequence which exist in str1 but not on str2.
	#   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
	#   but its length more than 3.
	#   --------------------------------------------------------
	#   Ans = 3
	task.uncommonSubsequence(str1, str2)
	#  Case D
	str1 = "fbi"
	str2 = "ice"
	#   Example 4
	#   str1 = fbi
	#   str2 = ice
	#   ------------
	#    [f,b,fb,fbi]
	#    Subsequences which is exist in str1 but not on str2.
	#   --------------------------------------------------------
	#   Ans = 1  [length of f or b]
	task.uncommonSubsequence(str1, str2)

if __name__ == "__main__": main()

Output

 String A :  aecb
 String B :  bace
  2
 String A :  ABCCDBE
 String B :  ABCCDBE
  0
 String A :  CCCCCB
 String B :  CCB
  3
 String A :  fbi
 String B :  ice
  1
#    Ruby program for
#    Shortest uncommon subsequence using dynamic programming
class Subsequence 
	def minValue(a, b) 
		if (a < b) 
			return a
		end

		return b
	end

	#  Find the length of shortest uncommon subsequence which is exist
	#  In str1 but not in str2.
	def uncommonSubsequence(str1, str2) 
		#  Get the length
		m = str1.length
		n = str2.length
		#  Auxiliary space
		dp = Array.new(m + 1) {Array.new(n + 1) {0}}
		result = 0
		max = (2 ** (0. size * 8 - 2))
		#  Reduce size of max by length of longest substring
		if (n > m) 
			max -= n
		else
 
			max -= m
		end

		i = 0
		while (i <= m) 
			dp[i][0] = 1
			i += 1
		end

		i = 0
		while (i <= n) 
			dp[0][i] = max
			i += 1
		end

		i = 1
		while (i <= m) 
			j = 1
			while (j <= n) 
				k = j - 1
				while (k >= 0 && str2[k] != str1[i - 1]) 
					k -= 1
				end

				if (k == -1) 
					dp[i][j] = 1
				else
 
					dp[i][j] = self.minValue(
                      dp[i - 1][j], dp[i - 1][k] + 1
                    )
				end

				j += 1
			end

			i += 1
		end

		if (dp[m][n] != max) 
			result = dp[m][n]
		end

		#  Display given strings
		print(" String A : ", str1, "\n")
		print(" String B : ", str2, "\n")
		#  Display calculated result
		print(" ", result, "\n")
	end

end

def main() 
	task = Subsequence.new()
	str1 = "aecb"
	str2 = "bace"
	#  Case A
	#   Example 1
	#   str1 = aecb
	#   str2 = bace
	#   ------------
	#    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
	#            str1 but not str2
	#    --------------------------------------------
	#    Length of shortest subsequence is 2
	#    Ans = 2
	task.uncommonSubsequence(str1, str2)
	#  Case B
	str1 = "ABCCDBE"
	str2 = "ABCCDBE"
	#   Example 2
	#   str1 = ABCCDBE
	#   str2 = ABCCDBE
	#   ------------
	#   all subsequence str1 exist in str2
	task.uncommonSubsequence(str1, str2)
	#  Case C
	str1 = "CCCCCB"
	str2 = "CCB"
	#   Example 3
	#   str1 = CCCCCB
	#   str2 = CCB
	#   ------------
	#   'CCC' Shortest subsequence which exist in str1 but not on str2.
	#   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
	#   but its length more than 3.
	#   --------------------------------------------------------
	#   Ans = 3
	task.uncommonSubsequence(str1, str2)
	#  Case D
	str1 = "fbi"
	str2 = "ice"
	#   Example 4
	#   str1 = fbi
	#   str2 = ice
	#   ------------
	#    [f,b,fb,fbi]
	#    Subsequences which is exist in str1 but not on str2.
	#   --------------------------------------------------------
	#   Ans = 1  [length of f or b]
	task.uncommonSubsequence(str1, str2)
end

main()

Output

 String A : aecb
 String B : bace
 2
 String A : ABCCDBE
 String B : ABCCDBE
 0
 String A : CCCCCB
 String B : CCB
 3
 String A : fbi
 String B : ice
 1

/*
    Scala program for
    Shortest uncommon subsequence using dynamic programming
*/
class Subsequence()
{
	def minValue(a: Int, b: Int): Int = {
		if (a < b)
		{
			return a;
		}
		return b;
	}
	// Find the length of shortest uncommon subsequence which is exist
	// In str1 but not in str2.
	def uncommonSubsequence(str1: String, str2: String): Unit = {
		// Get the length
		var m: Int = str1.length();
		var n: Int = str2.length();
		// Auxiliary space
		var dp: Array[Array[Int]] = Array.fill[Int](m + 1, n + 1)(0);
		var result: Int = 0;
		var max: Int = Int.MaxValue;
		// Reduce size of max by length of longest substring
		if (n > m)
		{
			max -= n;
		}
		else
		{
			max -= m;
		}
		var i: Int = 0;
		while (i <= m)
		{
			dp(i)(0) = 1;
			i += 1;
		}
		i = 0;
		while (i <= n)
		{
			dp(0)(i) = max;
			i += 1;
		}
		i = 1;
		while (i <= m)
		{
			var j: Int = 1;
			while (j <= n)
			{
				var k: Int = j - 1;
				while (k >= 0 && str2.charAt(k) != str1.charAt(i - 1))
				{
					k -= 1;
				}
				if (k == -1)
				{
					dp(i)(j) = 1;
				}
				else
				{
					dp(i)(j) = minValue(dp(i - 1)(j), dp(i - 1)(k) + 1);
				}
				j += 1;
			}
			i += 1;
		}
		if (dp(m)(n) != max)
		{
			result = dp(m)(n);
		}
		// Display given strings
		println(" String A : " + str1);
		println(" String B : " + str2);
		// Display calculated result
		println(" " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subsequence = new Subsequence();
		var str1: String = "aecb";
		var str2: String = "bace";
		// Case A
		/*
		   Example 1
		   str1 = aecb
		   str2 = bace
		   ------------
		    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
		            str1 but not str2
		    --------------------------------------------
		    Length of shortest subsequence is 2
		    Ans = 2
		*/
		task.uncommonSubsequence(str1, str2);
		// Case B
		str1 = "ABCCDBE";
		str2 = "ABCCDBE";
		/*
		   Example 2
		   
		   str1 = ABCCDBE
		   str2 = ABCCDBE
		   ------------
		   all subsequence str1 exist in str2
		*/
		task.uncommonSubsequence(str1, str2);
		// Case C
		str1 = "CCCCCB";
		str2 = "CCB";
		/*
		   Example 3
		   
		   str1 = CCCCCB
		   str2 = CCB
		   ------------
		   'CCC' Shortest subsequence which exist in str1 but not on str2.
		   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
		   but its length more than 3.
		   --------------------------------------------------------
		   Ans = 3
		*/
		task.uncommonSubsequence(str1, str2);
		// Case D
		str1 = "fbi";
		str2 = "ice";
		/*
		   Example 4
		   
		   str1 = fbi
		   str2 = ice
		   ------------
		    [f,b,fb,fbi]
		    Subsequences which is exist in str1 but not on str2.
		   --------------------------------------------------------
		   Ans = 1  [length of f or b]
		*/
		task.uncommonSubsequence(str1, str2);
	}
}

Output

 String A : aecb
 String B : bace
 2
 String A : ABCCDBE
 String B : ABCCDBE
 0
 String A : CCCCCB
 String B : CCB
 3
 String A : fbi
 String B : ice
 1
import Foundation;
/*
    Swift 4 program for
    Shortest uncommon subsequence using dynamic programming
*/
class Subsequence
{
	func minValue(_ a: Int, _ b: Int) -> Int
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	// Find the length of shortest uncommon subsequence which is exist
	// In str1 but not in str2.
	func uncommonSubsequence(_ s1: String, _ s2: String)
	{
      	let str1 = Array(s1);
        let str2 = Array(s2);
		// Get the length
		let m: Int = str1.count;
		let n: Int = str2.count;
		// Auxiliary space
		var dp: [
			[Int]
		] = Array(
          repeating: Array(repeating: 0, count: n + 1), count: m + 1
      	);
		var result: Int = 0;
		var max: Int = Int.max;
		// Reduce size of max by length of longest substring
		if (n > m)
		{
			max -= n;
		}
		else
		{
			max -= m;
		}
		var i: Int = 0;
		while (i <= m)
		{
			dp[i][0] = 1;
			i += 1;
		}
		i = 0;
		while (i <= n)
		{
			dp[0][i] = max;
			i += 1;
		}
		i = 1;
		while (i <= m)
		{
			var j: Int = 1;
			while (j <= n)
			{
				var k: Int = j - 1;
				while (k >= 0 && str2[k]  != str1[i - 1])
				{
					k -= 1;
				}
				if (k == -1)
				{
					dp[i][j] = 1;
				}
				else
				{
					dp[i][j] = self.minValue(
                      dp[i - 1][j], dp[i - 1][k] + 1
                    );
				}
				j += 1;
			}
			i += 1;
		}
		if (dp[m][n]  != max)
		{
			result = dp[m][n];
		}
		// Display given strings
		print(" String A : ", s1);
		print(" String B : ", s2);
		// Display calculated result
		print(" ", result);
	}
}
func main()
{
	let task: Subsequence = Subsequence();
	var str1: String = "aecb";
	var str2: String = "bace";
	// Case A
	/*
	   Example 1
	   str1 = aecb
	   str2 = bace
	   ------------
	    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
	            str1 but not str2
	    --------------------------------------------
	    Length of shortest subsequence is 2
	    Ans = 2
	*/
	task.uncommonSubsequence(str1, str2);
	// Case B
	str1 = "ABCCDBE";
	str2 = "ABCCDBE";
	/*
	   Example 2
	   
	   str1 = ABCCDBE
	   str2 = ABCCDBE
	   ------------
	   all subsequence str1 exist in str2
	*/
	task.uncommonSubsequence(str1, str2);
	// Case C
	str1 = "CCCCCB";
	str2 = "CCB";
	/*
	   Example 3
	   
	   str1 = CCCCCB
	   str2 = CCB
	   ------------
	   'CCC' Shortest subsequence which exist in str1 but not on str2.
	   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
	   but its length more than 3.
	   --------------------------------------------------------
	   Ans = 3
	*/
	task.uncommonSubsequence(str1, str2);
	// Case D
	str1 = "fbi";
	str2 = "ice";
	/*
	   Example 4
	   
	   str1 = fbi
	   str2 = ice
	   ------------
	    [f,b,fb,fbi]
	    Subsequences which is exist in str1 but not on str2.
	   --------------------------------------------------------
	   Ans = 1  [length of f or b]
	*/
	task.uncommonSubsequence(str1, str2);
}
main();

Output

 String A :  aecb
 String B :  bace
  2
 String A :  ABCCDBE
 String B :  ABCCDBE
  0
 String A :  CCCCCB
 String B :  CCB
  3
 String A :  fbi
 String B :  ice
  1
/*
    Kotlin program for
    Shortest uncommon subsequence using dynamic programming
*/
class Subsequence
{
	fun minValue(a: Int, b: Int): Int
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	// Find the length of shortest uncommon subsequence which is exist
	// In str1 but not in str2.
	fun uncommonSubsequence(str1: String, str2: String): Unit
	{
		// Get the length
		val m: Int = str1.length;
		val n: Int = str2.length;
		// Auxiliary space
		var dp: Array < Array < Int >> = Array(m + 1)
		{
			Array(n + 1)
			{
				0
			}
		};
		var result: Int = 0;
		var max: Int = Int.MAX_VALUE;
		// Reduce size of max by length of longest substring
		if (n > m)
		{
			max -= n;
		}
		else
		{
			max -= m;
		}
		var i: Int = 0;
		while (i <= m)
		{
			dp[i][0] = 1;
			i += 1;
		}
		i = 0;
		while (i <= n)
		{
			dp[0][i] = max;
			i += 1;
		}
		i = 1;
		while (i <= m)
		{
			var j: Int = 1;
			while (j <= n)
			{
				var k: Int = j - 1;
				while (k >= 0 && str2.get(k) != str1.get(i - 1))
				{
					k -= 1;
				}
				if (k == -1)
				{
					dp[i][j] = 1;
				}
				else
				{
					dp[i][j] = this.minValue(dp[i - 1][j], dp[i - 1][k] + 1);
				}
				j += 1;
			}
			i += 1;
		}
		if (dp[m][n] != max)
		{
			result = dp[m][n];
		}
		// Display given strings
		println(" String A : " + str1);
		println(" String B : " + str2);
		// Display calculated result
		println(" " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subsequence = Subsequence();
	var str1: String = "aecb";
	var str2: String = "bace";
	// Case A
	/*
	   Example 1
	   str1 = aecb
	   str2 = bace
	   ------------
	    [ab,cb,eb,aecb,acb,ecb] Subsequences exists in 
	            str1 but not str2
	    --------------------------------------------
	    Length of shortest subsequence is 2
	    Ans = 2
	*/
	task.uncommonSubsequence(str1, str2);
	// Case B
	str1 = "ABCCDBE";
	str2 = "ABCCDBE";
	/*
	   Example 2
	   
	   str1 = ABCCDBE
	   str2 = ABCCDBE
	   ------------
	   all subsequence str1 exist in str2
	*/
	task.uncommonSubsequence(str1, str2);
	// Case C
	str1 = "CCCCCB";
	str2 = "CCB";
	/*
	   Example 3
	   
	   str1 = CCCCCB
	   str2 = CCB
	   ------------
	   'CCC' Shortest subsequence which exist in str1 but not on str2.
	   Note ['CCCC',CCCCCB,CCCCB] is also uncommon subsequence 
	   but its length more than 3.
	   --------------------------------------------------------
	   Ans = 3
	*/
	task.uncommonSubsequence(str1, str2);
	// Case D
	str1 = "fbi";
	str2 = "ice";
	/*
	   Example 4
	   
	   str1 = fbi
	   str2 = ice
	   ------------
	    [f,b,fb,fbi]
	    Subsequences which is exist in str1 but not on str2.
	   --------------------------------------------------------
	   Ans = 1  [length of f or b]
	*/
	task.uncommonSubsequence(str1, str2);
}

Output

 String A : aecb
 String B : bace
 2
 String A : ABCCDBE
 String B : ABCCDBE
 0
 String A : CCCCCB
 String B : CCB
 3
 String A : fbi
 String B : ice
 1
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