LeetCode 522 - Longest Uncommon Subsequence II

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Two Pointers, String, Sorting

Solution

Problem Understanding

The problem asks us to find the length of the longest string in the array that is not a subsequence of any other string in the same array.

A subsequence is formed by deleting zero or more characters from a string without changing the order of the remaining characters. For example, "abc" is a subsequence of "axbyc" because we can remove the extra characters and keep the order intact.

The key detail is that we are not searching for a substring. Characters do not need to be contiguous. Only the relative order matters.

The input is an array of strings, strs. We must determine whether each string can appear as a subsequence inside another string in the array. If a string is unique in this sense, meaning it is not a subsequence of any other string, then it is considered an uncommon subsequence.

The expected output is the length of the longest such string. If every string is a subsequence of another string, then we return -1.

The constraints are relatively small:

The number of strings is at most 50
Each string length is at most 10

These constraints are extremely important because they allow us to use pairwise comparisons between strings without performance concerns. Even algorithms with cubic behavior are acceptable at this scale.

Several edge cases are important:

Duplicate strings immediately disqualify themselves, because each copy is a subsequence of the other.
A very short string may be a subsequence of many longer strings.
A string is always a subsequence of itself, so when comparing strings we must carefully avoid treating a single occurrence as invalid unless another identical string exists.
If all strings are duplicates or subsequences of others, the answer becomes -1.

Approaches

Brute Force Approach

The brute force idea is to generate every possible subsequence of every string, then determine which subsequences appear uniquely.

For a string of length n, there are 2^n possible subsequences. Since string lengths are at most 10, one string can generate up to 1024 subsequences. We could store all subsequences in a hash map and count how many strings contain them.

After generating all subsequences, we would look for the longest subsequence that appears in exactly one string.

This approach is correct because it explicitly examines every possible subsequence and checks uniqueness directly.

However, it is unnecessarily expensive and complicated. Even though the constraints are small enough to technically allow it, generating all subsequences creates extra work and increases implementation complexity.

Optimal Approach

The important observation is that the answer itself must be one of the original strings.

Suppose some subsequence x is uncommon. Then x comes from some original string s. Since x is a subsequence of s, and s is at least as long as x, if s itself is not a subsequence of any other string, then s is a better candidate than x.

This means we never need to generate subsequences at all. We only need to determine whether each original string is a subsequence of any other string.

The algorithm becomes:

For every string strs[i]
Compare it against every other string strs[j]
Check whether strs[i] is a subsequence of strs[j]
If it is never a subsequence of another string, update the answer

Because the constraints are tiny, pairwise subsequence checking is completely feasible.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × 2^m × m)	O(2^m)	Generates all subsequences explicitly
Optimal	O(n² × m)	O(1)	Directly checks each string against all others

Here:

n is the number of strings
m is the maximum string length

Since m <= 10, the optimal approach is extremely efficient in practice.

Algorithm Walkthrough

Initialize a variable longest_length to -1.

This variable stores the best uncommon subsequence length found so far. If no valid string exists, it remains -1. 2. Iterate through every string in the array.

For each string current_string, we will determine whether it is a subsequence of any other string. 3. Assume the current string is uncommon.

Create a boolean flag such as is_uncommon = True. 4. Compare the current string against every other string.

For each comparison:

Skip comparing the string with itself at the same index
Check whether current_string is a subsequence of other_string

Use the two-pointer subsequence check.

Maintain two pointers:

One pointer for the candidate subsequence
One pointer for the target string

Move through the target string character by character.

Whenever characters match, advance the subsequence pointer.

If the subsequence pointer reaches the end, the candidate is a subsequence. 6. If the current string is a subsequence of another string, mark it invalid.

Set is_uncommon = False and stop checking further strings. 7. If the string remains uncommon after all comparisons, update the answer.

Since we want the maximum length:

longest_length = max(longest_length, len(current_string))

After processing all strings, return longest_length.

Why it works

The algorithm works because an uncommon subsequence must originate from one of the original strings. If an original string is not a subsequence of any other string, then it itself is a valid uncommon subsequence.

By checking every string against all others, we correctly determine whether it is unique in the subsequence sense. Since we track the maximum valid length, the final answer is guaranteed to be the longest uncommon subsequence.

Python Solution

from typing import List

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def is_subsequence(subsequence: str, target: str) -> bool:
            sub_index = 0
            target_index = 0

            while sub_index < len(subsequence) and target_index < len(target):
                if subsequence[sub_index] == target[target_index]:
                    sub_index += 1
                target_index += 1

            return sub_index == len(subsequence)

        longest_length = -1

        for i, current_string in enumerate(strs):
            is_uncommon = True

            for j, other_string in enumerate(strs):
                if i == j:
                    continue

                if is_subsequence(current_string, other_string):
                    is_uncommon = False
                    break

            if is_uncommon:
                longest_length = max(longest_length, len(current_string))

        return longest_length

The implementation starts by defining a helper function called is_subsequence. This function uses the standard two-pointer technique.

The first pointer traverses the candidate subsequence, while the second pointer traverses the target string. Whenever matching characters are found, the subsequence pointer advances. If we successfully consume the entire subsequence, then the subsequence relationship holds.

The outer loop processes every string in the array as a potential answer candidate.

For each candidate string, the inner loop compares it against all other strings. If the candidate is found as a subsequence of another string, it is immediately rejected.

If the string survives all comparisons, it is a valid uncommon subsequence, and we update the maximum length.

The algorithm avoids generating subsequences entirely, which keeps the implementation concise and efficient.

Go Solution

func findLUSlength(strs []string) int {
	isSubsequence := func(subsequence string, target string) bool {
		subIndex := 0
		targetIndex := 0

		for subIndex < len(subsequence) && targetIndex < len(target) {
			if subsequence[subIndex] == target[targetIndex] {
				subIndex++
			}
			targetIndex++
		}

		return subIndex == len(subsequence)
	}

	longestLength := -1

	for i, currentString := range strs {
		isUncommon := true

		for j, otherString := range strs {
			if i == j {
				continue
			}

			if isSubsequence(currentString, otherString) {
				isUncommon = false
				break
			}
		}

		if isUncommon && len(currentString) > longestLength {
			longestLength = len(currentString)
		}
	}

	return longestLength
}

The Go implementation follows exactly the same logic as the Python version.

One difference is that Go strings are indexed as byte slices. Since the problem guarantees lowercase English letters only, byte indexing is perfectly safe.

The subsequence helper function is implemented as an inline closure for clarity. The rest of the solution uses nested loops exactly like the Python version.

Go does not require special handling for integer overflow here because string lengths are extremely small.

Worked Examples

Example 1

Input: ["aba", "cdc", "eae"]

We examine each string individually.

Checking `"aba"`

Compared Against	Is `"aba"` a subsequence?
`"cdc"`	No
`"eae"`	No

Since "aba" is not a subsequence of any other string, it is uncommon.

Current answer:

max(-1, 3) = 3

Checking `"cdc"`

Compared Against	Is `"cdc"` a subsequence?
`"aba"`	No
`"eae"`	No

"cdc" is also uncommon.

Current answer remains:

max(3, 3) = 3

Checking `"eae"`

Compared Against	Is `"eae"` a subsequence?
`"aba"`	No
`"cdc"`	No

"eae" is uncommon as well.

Final answer:

Example 2

Input: ["aaa", "aaa", "aa"]

Checking first `"aaa"`

Compared Against	Is subsequence?
second `"aaa"`	Yes

Immediately invalid.

Checking second `"aaa"`

Compared Against	Is subsequence?
first `"aaa"`	Yes

Also invalid.

Checking `"aa"`

Compared Against	Is subsequence?
`"aaa"`	Yes

Also invalid.

No valid uncommon subsequence exists.

Final answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² × m)	Compare every pair of strings, each subsequence check takes O(m)
Space	O(1)	Only a few variables are used

The algorithm performs pairwise comparisons among all strings. For each pair, the subsequence check scans at most m characters.

Since n <= 50 and m <= 10, the total work is extremely small in practice.

The algorithm uses constant extra space because it does not allocate any auxiliary data structures proportional to the input size.

Test Cases

solution = Solution()

assert solution.findLUSlength(["aba", "cdc", "eae"]) == 3  # basic example
assert solution.findLUSlength(["aaa", "aaa", "aa"]) == -1  # duplicates invalidate answer

assert solution.findLUSlength(["a", "b", "c"]) == 1  # all unique single chars
assert solution.findLUSlength(["a", "a", "b"]) == 1  # one duplicate, one unique
assert solution.findLUSlength(["abc", "abc", "abc"]) == -1  # all identical

assert solution.findLUSlength(["abc", "defgh", "abcd"]) == 5  # longest unique string
assert solution.findLUSlength(["aabbcc", "aabbcc", "cb"]) == 2  # shorter uncommon string
assert solution.findLUSlength(["abcd", "abc", "ab", "a"]) == 4  # longest string wins

assert solution.findLUSlength(["aaa", "aa", "a"]) == 3  # longest string not subsequence of others
assert solution.findLUSlength(["abcde", "ace", "bd"]) == 5  # full string valid

assert solution.findLUSlength(["abc", "xbc", "xxbc"]) == 4  # longest unique candidate
assert solution.findLUSlength(["abc", "abcde", "ace"]) == 5  # subsequence nested inside longer string

assert solution.findLUSlength(["a", "a"]) == -1  # minimal duplicate case
assert solution.findLUSlength(["ab", "ba"]) == 2  # neither subsequence of the other

Test	Why
`["aba", "cdc", "eae"]`	Verifies standard valid case
`["aaa", "aaa", "aa"]`	Verifies duplicate invalidation
`["a", "b", "c"]`	All strings uncommon
`["a", "a", "b"]`	Single remaining uncommon string
`["abc", "abc", "abc"]`	Entire array duplicates
`["abc", "defgh", "abcd"]`	Longest valid uncommon string
`["aabbcc", "aabbcc", "cb"]`	Shorter string becomes answer
`["abcd", "abc", "ab", "a"]`	Longest string dominates
`["aaa", "aa", "a"]`	Longer repeated characters
`["abcde", "ace", "bd"]`	Nested subsequences
`["abc", "xbc", "xxbc"]`	Different lengths and structures
`["abc", "abcde", "ace"]`	Longer string remains valid
`["a", "a"]`	Smallest duplicate input
`["ab", "ba"]`	Same length, different order

Edge Cases

Duplicate Strings

A duplicated string is always a subsequence of another identical string. This is one of the most common sources of bugs because developers sometimes forget that matching another copy invalidates the candidate.

For example:

["abc", "abc"]

Both strings fail because each is a subsequence of the other. The implementation handles this correctly by comparing indices rather than values alone.

Very Short Strings

Single-character strings can easily become subsequences of longer strings.

For example:

["a", "abc"]

The string "a" is a subsequence of "abc", so it cannot be uncommon. The two-pointer subsequence check naturally handles this scenario.

All Strings Nested

Sometimes every shorter string is contained inside a longer string.

For example:

["abcd", "abc", "ab", "a"]

Only "abcd" qualifies because none of the others are unique in the subsequence sense. The algorithm correctly identifies the longest valid candidate by checking every pair independently.

LeetCode 522 - Longest Uncommon Subsequence II

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Checking "aba"

Checking "cdc"

Checking "eae"

Example 2

Checking first "aaa"

Checking second "aaa"

Checking "aa"

Complexity Analysis

Test Cases

Edge Cases

Duplicate Strings

Very Short Strings

All Strings Nested

Checking `"aba"`

Checking `"cdc"`

Checking `"eae"`

Checking first `"aaa"`

Checking second `"aaa"`

Checking `"aa"`