最长特殊序列 Ⅰ

难度: Easy

给你两个字符串 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 由小写英文字母组成

Submission

运行时间: 22 ms

内存: 16.0 MB

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

Explain

这个题解的思路是比较两个字符串a和b的长度。如果长度不相等，直接返回较长字符串的长度，因为较长的字符串必然包含另一个字符串不具有的子序列。如果长度相等，进一步判断两个字符串是否相等。如果相等，说明它们的子序列完全相同，不存在特殊序列，返回-1。如果不相等，说明它们本身就是彼此的特殊序列，返回字符串的长度。

时间复杂度: O(la + lb)

空间复杂度: O(1)

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        la, lb = len(a), len(b)  # 计算字符串a和b的长度
        if la != lb:  # 如果长度不相等
            return max(la, lb)  # 返回较长字符串的长度
        if a == b:  # 如果两个字符串相等
            return -1  # 不存在特殊序列，返回-1
        else:  # 如果两个字符串不相等
            return la  # 返回字符串的长度，因为它们本身就是彼此的特殊序列

Explore

题目中的特殊序列指的是一个字符串的子序列中不存在于另一个字符串的子序列。当两个字符串长度相等且内容不同时，尽管它们可能有一些共同的子序列（例如单个字符或部分字符组合），但作为整体，它们本身就是对方没有的特殊序列。因此，它们本身是彼此的特殊序列。

对于长度相等但内容不同的字符串，不可能存在一个字符串是另一个字符串的子序列，因为子序列需要保持字符的相对顺序，长度相等意味着若一个字符串是另一个的子序列，则两者必须完全相同。因此，这种情况不会影响算法的输出，算法将返回这两个字符串的长度，因为它们本身就是特殊序列。

此算法基于字符串长度和内容比较，不依赖于字符的具体类型，因此无论输入字符是ASCII字符、特殊符号还是不同语言的字符，算法都是有效的。不需要对字符串进行特殊的预处理，因为字符串比较操作本身已经支持不同类型的字符。

在实际应用中，可以解释为两个完全相同的字符串无法提供独特的子序列，因为任何子序列在另一个字符串中也同样存在。因此，它们没有特殊序列。这种情况下返回-1是一种约定，用于指示不存在满足条件的特殊序列。在文档或用户界面中，应明确说明当两个字符串完全相同时，将返回-1，代表没有找到独特的特殊序列。