Sunday, September 30, 2018

How to find Longest Uncommon Subsequence


Problem:  Given two strings, you have to find the length of longest uncommon subsequence of the two strings.

 

 What is longest uncommon subsequence?

   The longest uncommon subsequence is defined as the longest subsequence of one of these strings which is not a subsequence of other string. 
   
Example: 

Input:  "abcdef"    ,   "abc"
Output: 6
the longest subsequence is 6 because "abcdef" is a subsequence
of first string , but is not a subsequence of second string 

Input: "xy"  ,"xy"
Output:0
both strings are same , so there is not uncommon subsequence .
hence output is 0.
 

Greedy solution





# include<iostream>using namespace std;
int longest_uncommon_subsequence(string, string, int, int); // function define
int main()
{
    string str1, str2;
    cin >> str1 >> str2;
    int len1 = 0, len2 = 0;
    len1 = str1.length(); // find the length of first string
    len2 = str2.length(); // find the length of  second string
int ans = longest_uncommon_subsequence(str1, str2, len1, len2);
// this function  will return the length of  longest uncommon subsequence

    if (ans == 0)
    {
        cout << "0"; // if both string are equal
    }
    else    {
        cout << ans;
    }
}
int longest_uncommon_subsequence(string str1, string str2, int len1, int len2)
    {

    / * if length of first string is greater that mean subsequence of first string is longest
    uncommon * /

    if (len1 > len2)
        {
        return len1;
        }
        else if (len2 > len1)
        {
        return len2;
    }

    / * if both are of equal length that means we have to  check
    with comparing individual elements * /

    else    {
    int    flag = 0;
    for (int i=0;i < len1;i++)
        {
        if (str1[i] != str2[i])
        {
            flag = len1;
    break;
    }
    }
    return flag;
    }
    }




No comments: