522. Longest Uncommon Subsequence II

MediumArrayHash TableTwo PointersStringSorting
Leetcode Link

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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].

  6. 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.

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

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the minimum element can be found in:

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 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 Two pointers is a common interview technique

Sorting Summary

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫