522. Longest Uncommon Subsequence II
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 ofstrs[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 stringb
is a subsequence of stringa
. It iterates through both strings concurrently using two pointers,i
fora
andj
forb
. If characters match (a[i] == b[j]
), it moves the pointerj
forward. The function returnsTrue
if it reaches the end of stringb
, meaningb
is a subsequence ofa
. -
The main function
findLUSlength
initializes an answer variableans
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 arraystrs
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 stringstrs[j]
. If a match is found (meaningstrs[i]
is a subsequence ofstrs[j]
), we break out of the inner loop asstrs[i]
cannot be an uncommon subsequence. -
If
strs[i]
is not found to be a subsequence of any other string (j
reachesn
, the length ofstrs
), it meansstrs[i]
is uncommon. At this point, we updateans
with the maximum of its current value or the length ofstrs[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 EvaluatorExample 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 instrs
. No other string is"a"
, so"a"
is not a subsequence of any string other than itself. The answerans
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, updateans
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 compareans
to the length of"c"
. Theans
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 asm
, each check call could take up toO(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 thecheck
function. - The
check
function uses constant space aside from the input since it only uses simple counter variables (i
andj
), 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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.