Longest Uncommon Subsequence II

Longest Uncommon Subsequence II

What is this problem about?

The Longest Uncommon Subsequence II problem is the advanced, non-trick version of its predecessor. You are given an array of strings. You must find the length of the longest string in the array that is an uncommon subsequence—meaning it is NOT a subsequence of any other string in the entire array. If no such string exists, return -1.

Why is this asked in interviews?

This problem is a solid test of string manipulation, custom sorting, and helper functions. Unlike part I, this requires actual algorithmic work. Interviewers use it to see if you can break a larger problem into manageable helper methods (like a isSubsequence(str1, str2) function) and apply it efficiently across an array using Two Pointers or nested loops.

Algorithmic pattern used

The best approach involves Sorting and String Matching (Two Pointers). First, you sort the array of strings by length in descending order. Because you want the longest uncommon subsequence, the first string you find that isn't a subsequence of any other string is guaranteed to be your answer! You check each string against all other strings using a simple two-pointer isSubsequence helper function.

Example explanation

Strings: ["aba", "cdc", "eae"] Sort by length descending: ["aba", "cdc", "eae"]. Let's check "aba":

• Is "aba" a subsequence of "cdc"? No.
• Is "aba" a subsequence of "eae"? No. Since "aba" is not a subsequence of anything else, it is an uncommon subsequence. Because we sorted by length, its length (3) is the maximum possible.

Strings: ["aabbcc", "aabbcc", "cb"] Sort by length: ["aabbcc", "aabbcc", "cb"] Check "aabbcc" (index 0): It is identical to index 1. Thus, it IS a subsequence of another string. Invalid. Check "aabbcc" (index 1): Identical to index 0. Invalid. Check "cb": Is it a subsequence of "aabbcc"? Yes (the 'c' and 'b' are there). Invalid. Return -1.

Common mistakes candidates make

A common error is skipping the comparison if strings are identical. If the array contains ["xyz", "xyz"], neither can be the answer because they are subsequences of each other. Another mistake is writing a clunky, overly complex isSubsequence function. It should be a clean, 5-line while loop using two pointers.

Interview preparation tip

For the Longest Uncommon Subsequence II coding problem, make sure you can write an isSubsequence(s1, s2) helper function in your sleep. It's a fundamental building block: use pointer i for s1 and j for s2. If s1[i] == s2[j], increment both. Otherwise, just increment j. If i reaches the end of s1, it's a subsequence!