LC 521. 最长特殊序列 Ⅰ

题目描述

这是 LeetCode 上的 521. 最长特殊序列 Ⅰ ，难度为 简单。

给你两个字符串 a 和 b，请返回 这两个字符串中 最长的特殊序列 。如果不存在，则返回 $-1$ 。

「最长特殊序列」 定义如下：该序列为 某字符串独有的最长子序列（即不能是其他字符串的子序列） 。

字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。

例如，“abc” 是 “aebdc” 的子序列，因为您可以删除 “aebdc” 中的下划线字符来得到 “abc” 。 “aebdc” 的子序列还包括 “aebdc” 、 “aeb” 和 “” (空字符串)。

示例 1：

输入: a = "aba", b = "cdc"

输出: 3

解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。

示例 2：

输入：a = "aaa", b = "bbb"

输出：3

解释: 最长特殊序列是“aaa”和“bbb”。

示例 3：

输入：a = "aaa", b = "aaa"

输出：-1

解释: 字符串a的每个子序列也是字符串b的每个子序列。同样，字符串b的每个子序列也是字符串a的子序列。

提示：

• $1 <= a.length, b.length <= 100$
• a 和 b 由小写英文字母组成

---

脑筋急转弯

当两字符串不同时，我们总能选择长度不是最小的字符串作为答案，而当两字符串相同时，我们无法找到特殊序列。

代码：

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

• 时间复杂度：字符串比较复杂度与长度成正比，复杂度为 $O(\max(n, m))$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.521 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。