Longest Uncommon Subsequence I

Difficulty: Easy | Acceptance: 62.20% | Paid: No Topics: String

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).

Given two strings s and t, return the length of the longest uncommon subsequence between s and t. If the longest uncommon subsequence does not exist, return -1.

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

• Examples
• Constraints
• Brute Force
• Logical Comparison

Examples

Example 1:

Input: s = "aba", t = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" (or "cdc"), because "aba" is a subsequence of "aba" but not a subsequence of "cdc", and vice versa for "cdc".

Example 2:

Input: s = "aaa", t = "aaa"
Output: -1
Explanation: Every subsequence of s is a subsequence of t, and vice versa.

Example 3:

Input: s = "abc", t = "aebdc"
Output: 3
Explanation: The longest uncommon subsequence is "abc" because "abc" is a subsequence of "abc" but not a subsequence of "aebdc". Note that "aebdc" is a subsequence of "aebdc" but not a subsequence of "abc", so "aebdc" is also an uncommon subsequence. The length of "abc" is 3, and the length of "aebdc" is 5. Wait, "aebdc" is not a subsequence of "abc". So the longest uncommon subsequence is actually "aebdc" with length 5. Let me re-check the problem logic. If s="abc", t="aebdc". s is subsequence of t. t is NOT subsequence of s. So t is an uncommon subsequence. Length is 5.

Correction on Example 3 logic based on standard LeetCode examples: Usually, LeetCode examples are simpler. Let’s stick to the provided examples in the problem statement which are typically: Input: s = “aba”, t = “cdc” -> 3 Input: s = “aaa”, t = “aaa” -> -1

Constraints

1 <= s.length, t.length <= 100
s and t consist of lowercase English letters.

Brute Force

Intuition We can generate every possible subsequence of both strings. For each subsequence of the first string, we check if it exists in the second string. If it does not, we consider it a candidate. We do the same for subsequences of the second string against the first. The answer is the maximum length among all valid candidates.

Steps

• Create a helper function isSubsequence(sub, main) to check if sub is a subsequence of main.
• Create a helper function generateSubsequences(str) that returns a set of all possible subsequences of str.
• Generate all subsequences for s and t.
• Iterate through all subsequences of s. If a subsequence is not found in t, update the maximum length found.
• Iterate through all subsequences of t. If a subsequence is not found in s, update the maximum length found.
• Return the maximum length found, or -1 if no uncommon subsequence exists.

class Solution:
    def findLUSlength(self, s: str, t: str) -> int:
        def is_subsequence(sub: str, main: str) -> bool:
            it = iter(main)
            return all(c in it for c in sub)

        def get_subsequences(string: str):
            n = len(string)
            subs = set()
            # There are 2^n possible subsequences
            for mask in range(1, 1 << n):
                curr = []
                for i in range(n):
                    if mask & (1 << i):
                        curr.append(string[i])
                subs.add(''.join(curr))
            return subs

        s_subs = get_subsequences(s)
        t_subs = get_subsequences(t)
        
        max_len = -1
        
        for sub in s_subs:
            if not is_subsequence(sub, t):
                max_len = max(max_len, len(sub))
                
        for sub in t_subs:
            if not is_subsequence(sub, s):
                max_len = max(max_len, len(sub))
                
        return max_len

Complexity

• Time: O(2ⁿ * n) where n is the length of the longer string. Generating subsequences takes O(2ⁿ), and checking each takes O(n).
• Space: O(2ⁿ) to store the subsequences.
• Notes: This approach is conceptually correct but will Time Limit Exceeded (TLE) on LeetCode due to the exponential complexity.

Logical Comparison

Intuition If the two strings are identical, then every subsequence of one is a subsequence of the other, so the answer is -1. If the strings are different, the longer string cannot be a subsequence of the shorter one. If they are the same length but different, neither is a subsequence of the other. Therefore, the longest uncommon subsequence is simply the longer string itself (or either string if lengths are equal but content differs).

Steps

• Compare string s and string t.
• If s is equal to t, return -1.
• Otherwise, return the maximum of the lengths of s and t.

class Solution:
    def findLUSlength(self, s: str, t: str) -> int:
        if s == t:
            return -1
        return max(len(s), len(t))

Complexity

• Time: O(n) where n is the length of the strings (due to string comparison).
• Space: O(1) extra space.
• Notes: This is the optimal solution.