522. Longest Uncommon Subsequence II

MediumArrayHash TableTwo PointersStringSorting

Problem Description

Given an array of strings named strs, the task is to find the length of the longest uncommon subsequence among the strings. A string is considered an uncommon subsequence if it is a subsequence of one of the strings in the array, but not a subsequence of any other strings in the array.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, abc is a subsequence of aebdc because you can remove the characters e and d to obtain abc.

If no such uncommon subsequence exists, the function should return -1.

Intuition

To solve this problem, the key observation is that if a string is not a subsequence of any other string, then it itself is the longest uncommon subsequence. We can compare strings to check whether one is a subsequence of another. We'll perform this comparison for each string in the array against all other strings.

Here's the approach:

We will compare each string (strs[i]) to every other string in the array to determine if it is a subsequence of any other string.
If strs[i] is found to be a subsequence of some other string, we know it cannot be the longest uncommon subsequence, so we move on to the next string.
If strs[i] is not a subsequence of any other strings, it is a candidate for the longest uncommon subsequence. We update our answer with the length of strs[i] if it is longer than our current answer.
We continue this process for all strings in the array, and in the end, we return the length of the longest uncommon subsequence found. If we don't find any, we return -1.

The reason why comparing subsequence relations works here is because a longer string containing the uncommon subsequence must itself be uncommon if none of the strings is a subsequence of another one. This means that the longest string that doesn't have any subsequences in common with others is effectively the longest uncommon subsequence.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The solution approach follows a brute-force strategy to check each string against all others to see if it is uncommon. Let's break it down step by step:

A helper function check(a, b) is defined to check if string b is a subsequence of string a. It iterates through both strings concurrently using two pointers, i for a and j for b. If characters match (a[i] == b[j]), it moves the pointer j forward. The function returns True if it reaches the end of string b, meaning b is a subsequence of a.
The main function findLUSlength initializes an answer variable ans with value -1. This will hold the length of the longest uncommon subsequence or -1 if no uncommon subsequence exists.
We iterate through each string strs[i] in the input array strs and for each string, we again iterate through the array to compare it against every other string.
During the inner iteration, we compare strs[i] to every other string strs[j]. If a match is found (meaning strs[i] is a subsequence of strs[j]), we break out of the inner loop as strs[i] cannot be an uncommon subsequence.
If strs[i] is not found to be a subsequence of any other string (j reaches n, the length of strs), it means strs[i] is uncommon. At this point, we update ans with the maximum of its current value or the length of strs[i].
After completing the iterations, we return the final value of ans as the result.

This solution uses no additional data structures, relying on iterations and comparisons to find the solution. The solution's time complexity is O(n^2 * m), where n is the number of strings and m is the length of the longest string. The space complexity is O(1) as no additional space is required besides the input array and pointers.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use the following small example to illustrate the solution approach:

Consider strs = ["a", "b", "aa", "c"]

Here is the step-by-step walkthrough of the above solution:

We will start with strs[0] which is "a". We compare "a" with every other string in strs. No other string is "a", so "a" is not a subsequence of any string other than itself. The answer ans is updated to max(-1, length("a")), which is 1.
Next, we look at strs[1], which is "b". Similar to the first step, compare "b" with every other string. Since it is unique and not a subsequence of any other string, ans becomes max(1, length("b")), which remains 1, since the length of "b" is also 1.
We then move on to strs[2], which is "aa". Repeat the same procedure. When comparing "aa" with other strings, we realize "aa" is not a subsequence of "a", "b", or "c". Therefore, update ans to max(1, length("aa")), which is 2 now.
Lastly, look at strs[3], which is "c". Again, since "c" isn't a subsequence of any other string in the array, we compare ans to the length of "c". The ans value remains 2 because max(2, length("c")) still equals 2.

After completing the iterations, since we have found uncommon subsequences, the final answer ans is 2, which is the length of the longest uncommon subsequence, "aa" from our array strs.

So, the function findLUSlength(["a", "b", "aa", "c"]) returns 2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findLUSlength(self, strs: List[str]) -> int:
5        # Helper function to check if string b is a subsequence of string a.
6        def is_subsequence(a: str, b: str) -> bool:
7            i = j = 0
8            while i < len(a) and j < len(b):
9                if a[i] == b[j]:
10                    j += 1    # Move to the next character in b if there's a match.
11                i += 1        # Move to the next character in a.
12            return j == len(b)  # Check if all characters in b are matched.
13
14        num_strings = len(strs)
15        longest_unique_length = -1  # Initialize with -1 as we may not find any unique strings.
16
17        # Iterate over each string in 'strs'.
18        for i in range(num_strings):
19            j = 0
20            # Compare the selected string with all other strings.
21            while j < num_strings:
22                # Skip if comparing the string with itself or if 'strs[j]' is not a subsequence of 'strs[i]'.
23                if i == j or not is_subsequence(strs[j], strs[i]):
24                    j += 1  # Move to the next string for comparison.
25                else:
26                    break  # 'strs[i]' is a subsequence of 'strs[j]', hence not unique.
27            # If we reached the end after comparisons, 'strs[i]' is unique.
28            if j == num_strings:
29                # Update the maximum length with the length of this unique string.
30                longest_unique_length = max(longest_unique_length, len(strs[i]))
31      
32        # Return the length of the longest uncommon subsequence.
33        return longest_unique_length
34

1class Solution {
2
3    // This method finds the length of the longest uncommon subsequence among the given array of strings.
4    public int findLUSlength(String[] strs) {
5        int longestLength = -1; // Initialize with -1 to account for no solution case.
6      
7        // We iterate over each string in the array to check if it's a non-subsequence of all other strings in the array.
8        for (int i = 0, j = 0, n = strs.length; i < n; ++i) {
9          
10            // We iterate over the strings again looking for a common subsequence.
11            for (j = 0; j < n; ++j) {
12                // We skip the case where we compare the string with itself.
13                if (i == j) {
14                    continue;
15                }
16              
17                // If the current string (strs[i]) is a subsequence of strs[j], then break out of this loop.
18                if (isSubsequence(strs[j], strs[i])) {
19                    break;
20                }
21            }
22          
23            // If we've gone through all strings without breaking, then strs[i] is not a subsequence of any other string.
24            if (j == n) {
25                // We update the longestLength if strs[i]'s length is greater than the current longestLength.
26                longestLength = Math.max(longestLength, strs[i].length());
27            }
28        }
29      
30        // Return the length of the longest uncommon subsequence. If there are none, return -1.
31        return longestLength;
32    }
33
34    // This private helper method checks if string b is a subsequence of string a.
35    private boolean isSubsequence(String a, String b) {
36        int j = 0; // This will be used to iterate over string b.
37
38        // Iterate over string a and string b to check if all characters of b are also in a in the same order.
39        for (int i = 0; i < a.length() && j < b.length(); ++i) {
40            // If we find a matching character, move to the next character in b.
41            if (a.charAt(i) == b.charAt(j)) {
42                ++j;
43            }
44        }
45
46        // After the loop, if j equals the length of b, it means all characters of b are found in a in order.
47        return j == b.length();
48    }
49}
50

1#include <vector>
2#include <string>
3#include <algorithm>
4
5using std::vector;
6using std::string;
7using std::max;
8
9class Solution {
10public:
11    // This function is to find the length of the longest uncommon subsequence among the strings.
12    // An uncommon subsequence does not appear as a subsequence in any other string.
13    int findLUSlength(vector<string>& strs) {
14        int longestUncommonLength = -1;  // Initialize the result with -1 to indicate no result.
15      
16        // Iterate over all strings in the array to find the longest uncommon subsequence.
17        for (int i = 0, j = 0, n = strs.size(); i < n; ++i) {
18            for (j = 0; j < n; ++j) {
19                if (i == j) continue;  // Skip comparing the string with itself.
20                // If current string strs[i] is a subsequence of strs[j], break and move to the next string.
21                if (isSubsequence(strs[j], strs[i])) break;
22            }
23            // If no subsequence is found in any other string, update the longest uncommon length.
24            if (j == n) longestUncommonLength = max(longestUncommonLength, (int)strs[i].size());
25        }
26        return longestUncommonLength;  // Return the length of the longest uncommon subsequence.
27    }
28
29private:
30    // This function checks if string 'b' is a subsequence of string 'a'.
31    bool isSubsequence(const string& a, const string& b) {
32        int indexB = 0;  // Index for iterating through string 'b'.
33        // Iterate over string 'a' with 'i' and string 'b' with 'indexB'.
34        for (int i = 0; i < a.size() && indexB < b.size(); ++i) {
35            if (a[i] == b[indexB]) ++indexB;  // If current chars are equal, move to the next char in 'b'.
36        }
37        // If 'indexB' reached the end of 'b', it means 'b' is a subsequence of 'a'.
38        return indexB == b.size();
39    }
40};
41

1// This function checks if string 'sub' is a subsequence of string 'main'.
2function isSubsequence(main: string, sub: string): boolean {
3    let subIndex: number = 0; // Index for iterating through the subsequence 'sub'.
4
5    // Iterate over the main string with 'i' and the subsequence with 'subIndex'.
6    for (let i = 0; i < main.length && subIndex < sub.length; i++) {
7        if (main.charAt(i) === sub.charAt(subIndex)) {
8            subIndex++; // If the current characters are equal, move to the next character in 'sub'.
9        }
10    }
11
12    // If 'subIndex' reached the end of 'sub', it means 'sub' is a subsequence of 'main'.
13    return subIndex === sub.length;
14}
15
16// This function finds the length of the longest uncommon subsequence among the strings.
17// An uncommon subsequence does not appear as a subsequence in any other string.
18function findLUSlength(strs: string[]): number {
19    let longestUncommonLength: number = -1; // Initialize the result with -1 to indicate no result.
20
21    // Iterate over all strings in the array to find the longest uncommon subsequence.
22    for (let i = 0, n = strs.length; i < n; i++) {
23        let j: number;
24        for (j = 0; j < n; j++) {
25            if (i === j) continue; // Skip comparing the string with itself.
26
27            // If current string strs[i] is a subsequence of strs[j], break and move to the next string.
28            if (isSubsequence(strs[j], strs[i])) break;
29        }
30
31        // If no subsequence is found in any other string, update the longest uncommon length.
32        if (j === n) {
33            longestUncommonLength = Math.max(longestUncommonLength, strs[i].length);
34        }
35    }
36
37    return longestUncommonLength; // Return the length of the longest uncommon subsequence.
38}
39

Time and Space Complexity

The provided code snippet defines the findLUSlength function, which finds the length of the longest uncommon subsequence among an array of strings. The time complexity and space complexity analysis for the code is as follows:

Time Complexity

The time complexity of the algorithm is O(n^2 * m), where n is the number of strings in the input list strs, and m is the length of the longest string among them.

Here's the justification for this complexity:

There are two nested loops, with the outer loop iterating over all strings (O(n)) and the inner loop potentially iterating over all other strings (O(n)) in the worst case.
Within the inner loop, the check function is called, which in worst-case compares two strings in linear time relative to their lengths. Since we're taking the length of the longest string as m, each check call could take up to O(m) time.

Hence, the multiplication of these factors leads to the O(n^2 * m) time complexity.

Space Complexity

The space complexity of the algorithm is O(1).

The explanation is as follows:

The extra space used in the algorithm includes constant space for variables i, j, ans, and the space used by the check function.
The check function uses constant space aside from the input since it only uses simple counter variables (i and j), which don't depend on the input size.

Thus, the overall space complexity is constant, regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don’t know