Shortest uncommon subsequence using dynamic programming
Dynamic programming is a powerful technique for solving optimization problems. In this article, we will explore the problem of finding the shortest uncommon subsequence between two strings using dynamic programming. We will discuss the problem statement, present an algorithm, provide a step-by-step solution, and analyze the time complexity of the code.
Problem Statement
The problem is to find the length of the shortest uncommon subsequence that exists in str1
but not in str2
. 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. The uncommon subsequence is the one that exists in str1
but is not a subsequence of str2
.
Algorithm
We can solve this problem using dynamic programming with the following steps:
- Initialize a 2D array
dp
of size(m + 1) x (n + 1)
, wherem
andn
are the lengths ofstr1
andstr2
respectively. - Set
max
to the maximum integer value. Reduce the size ofmax
by the length of the longest substring betweenstr1
andstr2
. - Initialize the first row of
dp
to 1, as an empty string is always a subsequence of any string. - Initialize the first column of
dp
tomax
, as it represents the case wherestr2
is an empty string and any non-empty subsequence ofstr1
would be uncommon. - Iterate over the remaining cells of
dp
(excluding the first row and column) and calculate the values based on the following rules: - If the characters at the current positions in
str1
andstr2
are the same, set the current cell value to the minimum of the previous row value and the previous diagonal cell value plus one. - If the characters are different, find the last occurrence of the character at the current position in
str1
instr2
. If it exists, set the current cell value to the minimum of the previous row value and the value at the last occurrence position plus one. Otherwise, set it to 1. - If the bottom-right cell of
dp
is not equal tomax
, it means there is an uncommon subsequence, and we assign its value toresult
.
Solution
/*
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
Explanation
Let's go through the code and understand how it solves the problem.
In the uncommonSubsequence
method, we start by initializing the variables and the 2D array dp
. The variable max
is set to the maximum integer value, and then it is reduced by the length of the longest substring between str1
and str2
. This is done to ensure that the length of the uncommon subsequence is not greater than the length of str1
or str2
.
We then initialize the first row of dp
to 1 because an empty string is always a subsequence of any string. The first column is initialized to max
because an empty str2
would make any non-empty subsequence of str1
uncommon.
Next, we iterate over the remaining cells of dp
and fill them based on the rules mentioned in the algorithm. We use the minValue
method to get the minimum value between two integers.
If the characters at the current positions in str1
and str2
are the same, we set the current cell value to the minimum of the previous row value (dp[i-1][j]
) and the previous diagonal cell value plus one (dp[i-1][k] + 1
), where k
is the last occurrence of the character in str2
.
If the characters are different, we search for the last occurrence of the character at the current position in str1
in str2
. If it exists, we set the current cell value to the minimum of the previous row value and the value at the last occurrence position plus one. Otherwise, we set it to 1.
After filling all the cells, we check if the bottom-right cell of dp
is equal to max
. If it is not, it means there is an uncommon subsequence, and we assign its value to the result
variable.
Finally, we display the given strings str1
and str2
, as well as the calculated result.
The output of the code matches the expected results for the given test cases.
Time Complexity
The time complexity of this algorithm is O(m * n)
, where m
and n
are the lengths of str1
and str2
respectively. This is because we have a nested loop that iterates over the cells of the dp
array.
As for the space complexity, it is O(m * n)
as well since we use a 2D array of the same size as the input strings.
Conclusion
In this article, we discussed the problem of finding the length of the shortest uncommon subsequence using dynamic programming. We explained the problem statement, presented an algorithm, and provided a step-by-step solution. We also analyzed the time complexity of the code. Dynamic programming is a powerful technique for solving optimization problems, and understanding how it can be applied to different scenarios helps us become better problem solvers.
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