How do you solve Longest Uncommon Subsequence II on LeetCode?

Longest Uncommon Subsequence II (LeetCode #522) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: A string can only be an uncommon subsequence if it is not a subsequence of any other string in the array.

What is the brute force solution for Longest Uncommon Subsequence II?

The brute force approach for Longest Uncommon Subsequence II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every string in the array to see if it can be a subsequence of any other string. If it can, we discard it; otherwise, we keep track of its length as a potential longest uncommon subsequence. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Longest Uncommon Subsequence II?

Longest Uncommon Subsequence II uses the following concepts: Array, Hash Table, Two Pointers, String, Sorting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Longest Uncommon Subsequence II?

Always clarify the definition of subsequence and uncommon subsequence before diving into coding. Think about edge cases and how they might affect your solution. Discuss your thought process and approach with the interviewer; they might provide hints or guidance.

What are common mistakes when solving Longest Uncommon Subsequence II?

Failing to check all strings against each other properly, leading to incorrect results. Not considering edge cases where all strings are the same or where one string is a subsequence of all others.

#522

Longest Uncommon Subsequence II

Medium

ArrayHash TableTwo PointersStringSortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(1)

💡

Intuition

Time O(n²)Space O(1)

The optimal solution leverages the fact that if a string is the longest, it cannot be a subsequence of any other string of equal or greater length. Thus, we can sort the strings by length and check only the longest strings for uniqueness.

⚙️

Algorithm

3 steps

1Step 1: Sort the strings by length in descending order.
2Step 2: For each string, check if it is a subsequence of any other string with the same or greater length.
3Step 3: If a string is not a subsequence of any other, return its length as the longest uncommon subsequence.

solution.py11 lines

1def is_subsequence(s1, s2):
2    it = iter(s2)
3    return all(c in it for c in s1)
4
5
6def findLUSlength(strs):
7    strs.sort(key=len, reverse=True)
8    for i in range(len(strs)):
9        if all(not is_subsequence(strs[i], strs[j]) for j in range(len(strs)) if i != j):
10            return len(strs[i])
11    return -1

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loops for checking subsequences. However, sorting the strings adds an additional O(n log n) factor, which is dominated by the subsequence checks. The space complexity is O(1) since we are not using any extra space beyond variables.

1A string can only be an uncommon subsequence if it is not a subsequence of any other string in the array.
2Sorting the strings by length helps in efficiently finding the longest uncommon subsequence.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.