# 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] = 1;
}
for (int i = 0; i <= n; i++)
{
dp[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)
{
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
*/
// Case B
str1 = "ABCCDBE";
str2 = "ABCCDBE";
/*
Example 2

str1 = ABCCDBE
str2 = ABCCDBE
------------
all subsequence str1 exist in 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
*/
// 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]
*/
}
}``````

#### 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] = 1;
}
for (int i = 0; i <= n; i++)
{
dp[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()
{
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
*/
// Case B
str1 = "ABCCDBE";
str2 = "ABCCDBE";
/*
Example 2

str1 = ABCCDBE
str2 = ABCCDBE
------------
all subsequence str1 exist in 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
*/
// 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]
*/
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)
{
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
*/
// Case B
str1 = "ABCCDBE";
str2 = "ABCCDBE";
/*
Example 2

str1 = ABCCDBE
str2 = ABCCDBE
------------
all subsequence str1 exist in 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
*/
// 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]
*/
}
}``````

#### 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] = 1
}
for i := 0 ; i <= n ; i++ {
dp[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] = 1;
}
for (\$i = 0; \$i <= \$n; \$i++)
{
\$dp[\$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()
{
\$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
*/
// Case B
\$str1 = "ABCCDBE";
\$str2 = "ABCCDBE";
/*
Example 2

str1 = ABCCDBE
str2 = ABCCDBE
------------
all subsequence str1 exist in 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
*/
// 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]
*/
}
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] = 1;
}
for (var i = 0; i <= n; i++)
{
dp[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 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
*/
// Case B
str1 = "ABCCDBE";
str2 = "ABCCDBE";
/*
Example 2

str1 = ABCCDBE
str2 = ABCCDBE
------------
all subsequence str1 exist in 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
*/
// 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]
*/
}
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 = [ * (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] = 1
i += 1

i = 0
while (i <= n) :
dp[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() :
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
#  Case B
str1 = "ABCCDBE"
str2 = "ABCCDBE"
#   Example 2
#   str1 = ABCCDBE
#   str2 = ABCCDBE
#   ------------
#   all subsequence str1 exist in 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
#  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]

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] = 1
i += 1
end

i = 0
while (i <= n)
dp[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()
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
#  Case B
str1 = "ABCCDBE"
str2 = "ABCCDBE"
#   Example 2
#   str1 = ABCCDBE
#   str2 = ABCCDBE
#   ------------
#   all subsequence str1 exist in 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
#  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]
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
*/
// Case B
str1 = "ABCCDBE";
str2 = "ABCCDBE";
/*
Example 2

str1 = ABCCDBE
str2 = ABCCDBE
------------
all subsequence str1 exist in 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
*/
// 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]
*/
}
}``````

#### 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] = 1;
i += 1;
}
i = 0;
while (i <= n)
{
dp[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()
{
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
*/
// Case B
str1 = "ABCCDBE";
str2 = "ABCCDBE";
/*
Example 2

str1 = ABCCDBE
str2 = ABCCDBE
------------
all subsequence str1 exist in 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
*/
// 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]
*/
}
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] = 1;
i += 1;
}
i = 0;
while (i <= n)
{
dp[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
{
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
*/
// Case B
str1 = "ABCCDBE";
str2 = "ABCCDBE";
/*
Example 2

str1 = ABCCDBE
str2 = ABCCDBE
------------
all subsequence str1 exist in 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
*/
// 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]
*/
}``````

#### 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`````` ## 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.