algoadvance

Leetcode: Longest Uncommon Subsequence I

Given two strings a and b, return the length of the longest uncommon subsequence between a and b. 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” but “aed” is not. An uncommon subsequence between a and b is a string that is a subsequence of one but not the other.

Clarifying Questions

  1. Can the input strings be empty?
    • Yes, according to the problem constraints, the strings can be empty.
  2. What is the length range of the strings?
    • The length of a and b can be at most 100.
  3. Are the strings composed of only lowercase English letters?
    • Yes, the problem guarantees that both strings contain only lowercase English letters.
  4. Are there any specific edge cases we should consider?
    • Yes, edge cases where one or both strings are empty.

Strategy

  1. Compare the Strings Directly:
    • If the strings a and b are not the same, the longest uncommon subsequence is the longer string because it cannot be a subsequence of the other string. If they are the same, there is no uncommon subsequence, so the result is -1.
  2. Implementation Steps:
    • Check if a is equal to b.
    • If they are equal, return -1.
    • If they are not equal, return the maximum length between a and b.

Code

def findLUSlength(a: str, b: str) -> int:
    if a == b:
        return -1
    else:
        return max(len(a), len(b))

# Example test cases
print(findLUSlength("aba", "cdc"))  # Output: 3
print(findLUSlength("aaa", "bbb"))  # Output: 3
print(findLUSlength("aaa", "aaa"))  # Output: -1

Time Complexity

The time complexity of this solution is O(1) because:

So, the overall time complexity is constant, O(1).

Try our interview co-pilot at AlgoAdvance.com