Shortest Uncommon Subsequence

19 June 2025

0

Given two strings S and T, find the length of the shortest subsequence in S which is not a subsequence in T. If no such subsequence is possible, return -1. A subsequence is a sequence that appears in the same relative order, but is not necessarily contiguous. A string of length n has 2^n different possible subsequences.

String S of length m (1 <= m <= 1000)
String T of length n (1 <= n <= 1000)

Examples:

Input : S = “babab” T = “babba”
Output : 3
Explanation: The subsequence “aab” of length 3 is present in S but not in T.

Input : S = “abb” T = “abab”
Output : -1
Explanation: There is no subsequence that is present in S but not in T.

Brute Force Method

A simple approach will be to generate all the subsequences of string S and for each subsequence check if it is present in string T or not. Consider example 2 in which S = “abb”,
its subsequences are “”, ”a”, ”b”, ”ab”, ”bb”, ”abb” each of which is present in “abab”. The time complexity of this solution will be exponential.

Efficient (Dynamic Programming):

1. Optimal substructure: Consider two strings S and T of length m and n respectively & let the function to find the shortest uncommon subsequence be shortestSeq (char *S, char *T). For each character in S, if it is not present in T then that character is the answer itself.

Otherwise, if it is found at index k then we have the choice of either including it in the shortest uncommon subsequence or not.

If it is included answer = 1 + ShortestSeq( S + 1, T + k + 1) 
If not included answer =  ShortestSeq( S + 1, T) 
The minimum of the two is the answer.

Thus, we can see that this problem has optimal substructure properties as it can be solved by using solutions to subproblems.

2. Overlapping Subproblems: Following is a simple recursive implementation of the above problem.

C++

// A simple recursive C++ program to find shortest
// uncommon subsequence.
#include<bits/stdc++.h>
using namespace std;
 
#define MAX 1005
 
/* A recursive function to find the length of
   shortest uncommon subsequence*/
int shortestSeq(char *S, char *T, int m, int n)
{
    // S string is empty
    if (m == 0)
        return MAX;
 
    // T string is empty
    if (n <= 0)
        return 1;
 
    // Loop to search for current character
    int k;
    for (k=0; k < n; k++)
        if (T[k] == S[0])
            break;
 
    // char not found in T
    if (k == n)
        return 1;
 
    // Return minimum of following two
    // Not including current char in answer
    // Including current char
    return min(shortestSeq(S+1, T, m-1, n),
            1 + shortestSeq(S+1, T+k+1, m-1, n-k-1));
}
 
// Driver program to test the above function
int main()
{
    char S[] = "babab";
    char T[] = "babba";
    int m = strlen(S), n = strlen(T);
    int ans = shortestSeq(S, T, m, n);
    if (ans >= MAX)
       ans = -1;
    cout << "Length of shortest subsequence is: "
         << ans << endl;
    return 0;
}

Java

// A simple recursive Java program to find shortest
// uncommon subsequence.
import java.util.*;
 
class GFG
{
 
static final int MAX = 1005;
 
/* A recursive function to find the length of
shortest uncommon subsequence*/
static int shortestSeq(char []S, char []T, int m, int n)
{
    // S String is empty
    if (m == 0)
        return MAX;
 
    // T String is empty
    if (n <= 0)
        return 1;
 
    // Loop to search for current character
    int k;
    for (k = 0; k < n; k++)
        if (T[k] == S[0])
            break;
 
    // char not found in T
    if (k == n)
        return 1;
 
    // Return minimum of following two
    // Not including current char in answer
    // Including current char
    return Math.min(shortestSeq(Arrays.copyOfRange(S, 1, S.length), T, m - 1, n),
                    1 + shortestSeq(Arrays.copyOfRange(S, 1, S.length), 
                    Arrays.copyOfRange(T, k + 1, T.length), m - 1, n - k - 1));
}
 
// Driver code
public static void main(String[] args)
{
    char S[] = "babab".toCharArray();
    char T[] = "babba".toCharArray();
    int m = S.length, n = T.length;
    int ans = shortestSeq(S, T, m, n);
    if (ans >= MAX)
    ans = -1;
    System.out.print("Length of shortest subsequence is: "
        + ans +"\n");
}
}
 
// This code is contributed by Rajput-Ji

Python3

# A simple recursive Python 
# program to find shortest 
# uncommon subsequence. 
MAX = 1005
 
# A recursive function to 
# find the length of shortest 
# uncommon subsequence
def shortestSeq(S, T, m, n):
 
    # S String is empty 
    if m == 0:
        return MAX
 
    # T String is empty 
    if(n <= 0):
        return 1
 
    # Loop to search for 
    # current character 
    for k in range(n):
        if(T[k] == S[0]):
            break
 
    # char not found in T 
    if(k == n):
        return 1
 
    # Return minimum of following 
    # two Not including current 
    # char in answer Including 
    # current char 
    return min(shortestSeq(S[1 : ], T, m - 1, n), 
               1 + shortestSeq((S[1 : ]), T[k + 1 : ], 
                                m - 1, n - k - 1))
 
# Driver code 
S = "babab"
T = "babba"
 
m = len(S)
n = len(T)
ans = shortestSeq(S, T, m, n)
if(ans >= MAX):
    ans =- 1
print("Length of shortest subsequence is:", ans)
 
# This code is contributed by avanitrachhadiya2155

C#

// A simple recursive C# program to find shortest
// uncommon subsequence.
using System;
 
class GFG
{
 
static readonly int MAX = 1005;
 
/* A recursive function to find the length of
shortest uncommon subsequence*/
static int shortestSeq(char []S, char []T, int m, int n)
{
    // S String is empty
    if (m == 0)
        return MAX;
 
    // T String is empty
    if (n <= 0)
        return 1;
 
    // Loop to search for current character
    int k;
    for (k = 0; k < n; k++)
        if (T[k] == S[0])
            break;
 
    // char not found in T
    if (k == n)
        return 1;
 
    // Return minimum of following two
    // Not including current char in answer
    // Including current char
    char []St1 = new Char[S.Length - 1];
    Array.Copy(S, 1, St1, 0, S.Length - 1);
    char []St2 = new Char[S.Length - 1];
    Array.Copy(S, 1, St2, 0, S.Length - 1);
    char []Tt1 = new Char[T.Length - (k + 1)];
    Array.Copy(T, k + 1, Tt1, 0, T.Length - (k + 1));
    return Math.Min(shortestSeq(St1, T, m - 1, n),
                    1 + shortestSeq(St2, Tt1, m - 1, n - k - 1));
}
 
// Driver code
public static void Main(String[] args)
{
    char []S = "babab".ToCharArray();
    char []T = "babba".ToCharArray();
    int m = S.Length, n = T.Length;
    int ans = shortestSeq(S, T, m, n);
    if (ans >= MAX)
    ans = -1;
    Console.Write("Length of shortest subsequence is: "
        + ans +"\n");
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript code to implement the approach
const MAX = 1005
 
// A recursive function to
// find the length of shortest
// uncommon subsequence
function shortestSeq(S, T, m, n){
 
    // S String is empty
    if(m == 0)
        return MAX
 
    // T String is empty
    if(n <= 0)
        return 1
 
    let k;
 
    // Loop to search for
    // current character
    for(k=0;k<n;k++){
        if(T[k] == S[0])
            break
    }
 
    // char not found in T
    if(k == n)
        return 1
 
    // Return minimum of following
    // two Not including current
    // char in answer Including
    // current char
    return Math.min(shortestSeq(S.substring(1,), T, m - 1, n),
            1 + shortestSeq((S.substring(1,)), T.substring(k + 1,),
                                m - 1, n - k - 1))
}
 
// Driver code
let S = "babab"
let T = "babba"
 
let m = S.length
let n = T.length
let ans = shortestSeq(S, T, m, n)
if(ans >= MAX)
    ans =- 1
document.write("Length of shortest subsequence is: "+ ans,"</br>")
 
// This code is contributed by shinjanpatra
 
</script>

Output

Length of shortest subsequence is: 3

Time complexity: O(m*n),The time complexity of this algorithm is O(m*n), where m and n are the lengths of the two strings. This is because the algorithm uses a recursive approach to find the shortest uncommon subsequence which involves comparing each character of the two strings.

Auxiliary Space: O(m*n),The space complexity of this algorithm is also O(m*n) because we are using a two-dimensional array to store the result of the recursive call.

If we draw the complete recursion tree, then we can see that there are many subproblems that are solved again and again. So this problem has Overlapping Substructure property and re-computation of the same subproblems can be avoided by either using Memoization or Tabulation. The following is a tabulated implementation of the problem.

C++

// A dynamic programming based C++ program
// to find shortest uncommon subsequence.
#include<bits/stdc++.h>
using namespace std;
 
#define MAX 1005
 
// Returns length of shortest common subsequence
int shortestSeq(char *S, char *T)
{
    int m = strlen(S), n = strlen(T);
 
    // declaring 2D array of m + 1 rows and
    // n + 1 columns dynamically
    int dp[m+1][n+1];
 
    // T string is empty
    for (int i = 0; i <= m; i++)
        dp[i][0] = 1;
 
    // S string is empty
    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++)
        {
            char ch = S[i-1];
            int k;
            for (k = j-1; k >= 0; k--)
                if (T[k] == ch)
                    break;
 
            // char not present in T
            if (k == -1)
                dp[i][j] = 1;
            else
               dp[i][j] = min(dp[i-1][j], dp[i-1][k] + 1);
        }
    }
 
    int ans = dp[m][n];
    if (ans >= MAX)
        ans = -1;
 
    return ans;
}
 
// Driver program to test the above function
int main()
{
    char S[] = "babab";
    char T[] = "babba";
    int m = strlen(S), n = strlen(T);
    cout << "Length of shortest subsequence is : "
         << shortestSeq(S, T) << endl;
}

Java

// A dynamic programming based Java program 
// to find shortest uncommon subsequence. 
import java.io.*;
class GFG 
{
 
    static final int MAX = 1005;
 
    // Returns length of shortest common subsequence 
    static int shortestSeq(char[] S, char[] T) 
    {
        int m = S.length, n = T.length;
 
        // declaring 2D array of m + 1 rows and 
        // n + 1 columns dynamically 
        int dp[][] = new int[m + 1][n + 1];
 
        // T string is empty 
        for (int i = 0; i <= m; i++) 
        {
            dp[i][0] = 1;
        }
 
        // S string is empty 
        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++) 
            {
                char ch = S[i - 1];
                int k;
                for (k = j - 1; k >= 0; k--)
                {
                    if (T[k] == ch)
                    {
                        break;
                    }
                }
 
                // char not present in T 
                if (k == -1) 
                {
                    dp[i][j] = 1;
                } 
                else
                {
                    dp[i][j] = Math.min(dp[i - 1][j],
                                    dp[i - 1][k] + 1);
                }
            }
        }
 
        int ans = dp[m][n];
        if (ans >= MAX) 
        {
            ans = -1;
        }
        return ans;
    }
 
    // Driver code 
    public static void main(String[] args) 
    {
        char S[] = "babab".toCharArray();
        char T[] = "babba".toCharArray();
        int m = S.length, n = T.length;
        System.out.println("Length of shortest" +
                            "subsequence is : " + 
                            shortestSeq(S, T));
    }
} 
 
// This code is contributed by 29AjayKumar

Python3

# A dynamic programming based Python program
# to find shortest uncommon subsequence.
MAX = 1005
 
# Returns length of shortest common subsequence
def shortestSeq(S: list, T: list):
    m = len(S)
    n = len(T)
 
    # declaring 2D array of m + 1 rows and
    # n + 1 columns dynamically
    dp = [[0 for i in range(n + 1)] 
             for j in range(m + 1)]
 
    # T string is empty
    for i in range(m + 1):
        dp[i][0] = 1
 
    # S string is empty
    for i in range(n + 1):
        dp[0][i] = MAX
 
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            ch = S[i - 1]
            k = j - 1
            while k >= 0:
                if T[k] == ch:
                    break
                k -= 1
 
            # char not present in T
            if k == -1:
                dp[i][j] = 1
            else:
                dp[i][j] = min(dp[i - 1][j], 
                               dp[i - 1][k] + 1)
 
    ans = dp[m][n]
    if ans >= MAX:
        ans = -1
 
    return ans
 
# Driver Code
if __name__ == "__main__":
    S = "babab"
    T = "babba"
 
    print("Length of shortest subsequence is:", 
                             shortestSeq(S, T))
 
# This code is contributed by
# sanjeev2552

C#

// A dynamic programming based C# program 
// to find shortest uncommon subsequence.
using System;
 
class GFG 
{
 
    static readonly int MAX = 1005;
 
    // Returns length of shortest common subsequence 
    static int shortestSeq(char[] S, char[] T) 
    {
        int m = S.Length, n = T.Length;
 
        // declaring 2D array of m + 1 rows and 
        // n + 1 columns dynamically 
        int [,]dp = new int[m + 1, n + 1];
 
        // T string is empty 
        for (int i = 0; i <= m; i++) 
        {
            dp[i, 0] = 1;
        }
 
        // S string is empty 
        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++) 
            {
                char ch = S[i - 1];
                int k;
                for (k = j - 1; k >= 0; k--)
                {
                    if (T[k] == ch)
                    {
                        break;
                    }
                }
 
                // char not present in T 
                if (k == -1) 
                {
                    dp[i, j] = 1;
                } 
                else
                {
                    dp[i, j] = Math.Min(dp[i - 1, j],
                                    dp[i - 1, k] + 1);
                }
            }
        }
 
        int ans = dp[m, n];
        if (ans >= MAX) 
        {
            ans = -1;
        }
        return ans;
    }
 
    // Driver code 
    public static void Main(String[] args) 
    {
        char []S = "babab".ToCharArray();
        char []T = "babba".ToCharArray();
        int m = S.Length, n = T.Length;
        Console.WriteLine("Length of shortest" +
                            "subsequence is : " + 
                            shortestSeq(S, T));
    }
}
 
// This code contributed by Rajput-Ji

PHP

<?php
// A dynamic programming based PHP program 
// to find shortest uncommon subsequence. 
 
$GLOBALS['MAX'] = 1005;
 
// Returns length of shortest
// common subsequence 
function shortestSeq($S, $T) 
{ 
    $m = strlen($S);
    $n = strlen($T); 
 
    // declaring 2D array of m + 1 rows  
    // and n + 1 columns dynamically 
    $dp = array(array()); 
 
    // T string is empty 
    for ($i = 0; $i <= $m; $i++) 
        $dp[$i][0] = 1; 
 
    // S string is empty 
    for ($i = 0; $i <= $n; $i++) 
        $dp[0][$i] = $GLOBALS['MAX']; 
 
    for ($i = 1; $i <= $m; $i++) 
    { 
        for ($j = 1; $j <= $n; $j++) 
        { 
            $ch = $S[$i - 1]; 
            for ($k = $j - 1; $k >= 0; $k--) 
                if ($T[$k] == $ch) 
                    break; 
 
            // char not present in T 
            if ($k == -1) 
                $dp[$i][$j] = 1; 
            else
            $dp[$i][$j] = min($dp[$i - 1][$j],  
                              $dp[$i - 1][$k] + 1); 
        } 
    } 
 
    $ans = $dp[$m][$n]; 
    if ($ans >= $GLOBALS['MAX']) 
        $ans = -1; 
 
    return $ans; 
} 
 
// Driver Code
$S = "babab"; 
$T = "babba"; 
$m = strlen($S);
$n = strlen($T); 
echo "Length of shortest subsequence is : ", 
                        shortestSeq($S, $T); 
 
// This code is contributed by Ryuga
?>

Javascript

<script>
 
// A dynamic programming based JavaScript program
// to find shortest uncommon subsequence.
 
 
const MAX = 1005
 
// Returns length of shortest common subsequence
function shortestSeq(S, T)
{
    let m = S.length, n = T.length;
 
    // declaring 2D array of m + 1 rows and
    // n + 1 columns dynamically
    let dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0));
 
    // T string is empty
    for (let i = 0; i <= m; i++)
        dp[i][0] = 1;
 
    // S string is empty
    for (let i = 0; i <= n; i++)
        dp[0][i] = MAX;
 
    for (let i = 1; i <= m; i++)
    {
        for (let j = 1; j <= n; j++)
        {
            let ch = S[i-1];
            let k;
            for (k = j-1; k >= 0; k--)
                if (T[k] == ch)
                    break;
 
            // char not present in T
            if (k == -1)
                dp[i][j] = 1;
            else
               dp[i][j] = Math.min(dp[i-1][j], dp[i-1][k] + 1);
        }
    }
 
    let ans = dp[m][n];
    if (ans >= MAX)
        ans = -1;
 
    return ans;
}
 
// Driver program to test the above function
 
let S = "babab";
let T = "babba";
let m = S.length, n = T.length;
document.write("Length of shortest subsequence is : "+shortestSeq(S, T),"</br>");
 
 
// This code is contributed by shinjanpatra
 
</script>

Output

Length of shortest subsequence is : 3

Time Complexity: O(m*n)
Auxiliary Space: O(m*n)

This article is contributed by Aditi Sharma. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Shortest Uncommon Subsequence

Brute Force Method

Efficient (Dynamic Programming):

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

PHP

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US