Skip to content

521. Longest Uncommon Subsequence I

DifficultyEasy

Description

Given two strings a and b, return the length of the longest uncommon subsequence between a and b. If no such uncommon subsequence exists, return -1.

An uncommon subsequence between two strings is a string that is a subsequence of exactly one of them.

 

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.

Example 2:

Input: a = "aaa", b = "bbb"
Output: 3
Explanation: The longest uncommon subsequences are "aaa" and "bbb".

Example 3:

Input: a = "aaa", b = "aaa"
Output: -1
Explanation: Every subsequence of string a is also a subsequence of string b. Similarly, every subsequence of string b is also a subsequence of string a. So the answer would be -1.

 

Constraints:

  • 1 <= a.length, b.length <= 100
  • a and b consist of lower-case English letters.

Solutions

Solution 1: Quick Thinking

Thinking

A subsequence is formed by deletions. If the two strings are equal, each remains a subsequence of the other, so no uncommon subsequence exists.

If they differ, the longer string cannot be a subsequence of the shorter one, so its length is the answer. Equality and length suffice; there is no need to enumerate subsequences.

If strings a and b are equal, then they have no special sequences, return -1; otherwise, return the length of the longer string.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the longer string among \(a\) and \(b\).

1
2
3
class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        return -1 if a == b else max(len(a), len(b))

1
2
3
4
5
class Solution {
    public int findLUSlength(String a, String b) {
        return a.equals(b) ? -1 : Math.max(a.length(), b.length());
    }
}

1
2
3
4
5
6
class Solution {
public:
    int findLUSlength(string a, string b) {
        return a == b ? -1 : max(a.size(), b.size());
    }
};

1
2
3
4
5
6
7
8
9
func findLUSlength(a string, b string) int {
    if a == b {
        return -1
    }
    if len(a) > len(b) {
        return len(a)
    }
    return len(b)
}

1
2
3
function findLUSlength(a: string, b: string): number {
    return a === b ? -1 : Math.max(a.length, b.length);
}

1
2
3
4
5
6
7
8
impl Solution {
    pub fn find_lu_slength(a: String, b: String) -> i32 {
        if a == b {
            return -1;
        }
        a.len().max(b.len()) as i32
    }
}

Comments