Longest Uncommon Subsequence I

easy string

Problem

Given two strings a and b, return the length of the longest uncommon subsequence — a subsequence of one string that is not a subsequence of the other. Return −1 if none exists.

Inputa = "aba", b = "cdc"

Output3

"aba" itself is a subsequence of a but not of b.

def find_lus_length(a, b):
    if a == b:
        return -1
    return max(len(a), len(b))

function findLUSlength(a, b) {
  if (a === b) return -1;
  return Math.max(a.length, b.length);
}

class Solution {
    public int findLUSlength(String a, String b) {
        if (a.equals(b)) return -1;
        return Math.max(a.length(), b.length());
    }
}

int findLUSlength(string a, string b) {
    if (a == b) return -1;
    return max((int)a.size(), (int)b.size());
}

Explanation

This problem looks scary because of the word "subsequence", but it has a surprising one-line answer. The whole thing comes down to a single observation.

Every string is a subsequence of itself. So the longest string we could hope to use is the longer of the two strings. A whole string can only be a subsequence of the other string if it equals it (when they are the same length) or is contained in it — but since both are full strings, the only way the longer one is "common" is if a and b are identical.

So if a == b, then any subsequence of one is also a subsequence of the other, and no uncommon subsequence exists — we return -1. Otherwise the answer is simply max(len(a), len(b)), the length of the longer string itself.

Example: a = "aba", b = "cdc". They are different, so the answer is max(3, 3) = 3 — the string "aba" is a subsequence of a but not of b.

Time: O(n) Space: O(1)