Given two strings a and b, find the length of the longest uncommon subsequence between them.

A subsequence of a string s is a string that can be obtained after deleting any number of characters from s. For example, “abc” is a subsequence of “aebdc” because you can delete the underlined characters in “aebdc” to get “abc”. Other subsequences of “aebdc” include “aebdc”, “aeb”, and “” (empty string).

An uncommon subsequence between two strings is a string that is a subsequence of one but not the other.

Return the length of the longest uncommon subsequence between a and b. If the longest uncommon subsequence doesn’t exist, return -1.

Example 1:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

Brute force solution

Iterate all the substring in two strings, try to check weather a substring exists in another string.

Time complexity: O(N^3).

class Solution {
public:
    int compare(string a, string b) {
        string ans;
        for(int i=0; i<a.size(); i++) {
            for(int j=i; j<a.size(); j++) {
                string sub = a.substr(i, j-i+1);
                if(b.find(sub) == std::string::npos) {
                    ans = sub.length() > ans.length() ? sub : ans;
                }
            }
        }
        return ans.length();
    }
    int findLUSlength(string a, string b) {
        int ab = compare(a, b);
        int ba = compare(b, a);
        int ans = max(ab, ba);
        return ans > 0 ? ans : -1;
    }
};

Clever solution

There are several scenarios:

• a = b, we will return -1
• a != b, in this case any specific one string is not the substring of another, so we return the string with a longer length.

So we can get a one-line solution:

class Solution {
public:
    int findLUSlength(string a, string b) {
        return a == b ? (-1) : max(a.length(), b.length());
    }
};

Preparing for an interview? Checkout this!