Jobs

Interviews

Discussions

Longest Uncommon Subsequence I

Easy

Google

1 view

Topics:

Strings

Given two strings a and b, return the length of the longest uncommon subsequence between a and b. If no such uncommon subsequence exists, return -1. An uncommon subsequence between two strings is a string that is a subsequence of exactly one of them.

Example 1:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

Example 2:

Input: a = "aaa", b = "bbb"
Output: 3
Explanation: The longest uncommon subsequences are "aaa" and "bbb".

Example 3:

Input: a = "aaa", b = "aaa"
Output: -1
Explanation: Every subsequence of string a is also a subsequence of string b. Similarly, every subsequence of string b is also a subsequence of string a. So the answer would be -1.

Constraints:

1 <= a.length, b.length <= 100
a and b consist of lowercase English letters.

Longest Uncommon Subsequence I

Easy

Google

1 view

Topics:

Strings

Example 1:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

Example 2:

Input: a = "aaa", b = "bbb"
Output: 3
Explanation: The longest uncommon subsequences are "aaa" and "bbb".

Example 3:

Input: a = "aaa", b = "aaa"
Output: -1
Explanation: Every subsequence of string a is also a subsequence of string b. Similarly, every subsequence of string b is also a subsequence of string a. So the answer would be -1.

Constraints:

1 <= a.length, b.length <= 100
a and b consist of lowercase English letters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings be empty or null?
What is the maximum length of the input strings?
Are the input strings case-sensitive (i.e., should 'abc' and 'Abc' be considered different)?
If no uncommon subsequence exists, what should the function return?
Are there any special characters or encoding considerations within the strings?

Brute Force Solution

Approach

The brute force approach means checking every single possibility to find the longest uncommon subsequence. It's like comparing each word against every other word, one by one, to see if one is a special part of the other.

Here's how the algorithm would work step-by-step:

First, check if the words are completely different. If they are, the longer word is the answer.
If the words are the same, there's no uncommon subsequence, so the answer is that there isn't one.
If the words are not completely different, then check if the first word is a special part of the second word. This means, can you make the first word by picking letters out of the second word, in the same order?
Also check the other way, is the second word a special part of the first word?
If neither word is a special part of the other, then the longer word is the answer.
If one word is a special part of the other, then the word that is not a special part is the answer. The algorithm must return the longest length possible given those criteria.

Code Implementation

def find_longest_uncommon_subsequence_length(first_string, second_string):
    # Check if the strings are identical
    if first_string == second_string:
        return -1

    first_string_length = len(first_string)
    second_string_length = len(second_string)

    # Determine if one string is a subsequence of the other
    if is_subsequence(first_string, second_string):
        return second_string_length

    # Determine if one string is a subsequence of the other
    if is_subsequence(second_string, first_string):
        return first_string_length

    # If neither is a subsequence of the other, return the length of the longer string
    return max(first_string_length, second_string_length)

def is_subsequence(shorter_string, longer_string):
    shorter_string_index = 0
    longer_string_index = 0

    while shorter_string_index < len(shorter_string) and longer_string_index < len(longer_string):
        if shorter_string[shorter_string_index] == longer_string[longer_string_index]:
            shorter_string_index += 1

        longer_string_index += 1

    # Check if all characters of shorter_string were found in longer_string
    return shorter_string_index == len(shorter_string)

Big(O) Analysis

Time Complexity

O(max(n, m)) – The algorithm's runtime is dominated by the string comparisons. First, the code checks if the strings are equal, which takes O(min(n, m)) time, where n and m are the lengths of the two strings. Then, it checks if one string is a subsequence of the other, which also takes at most O(max(n, m)) time. Since these operations are performed sequentially, the overall time complexity is O(min(n, m)) + O(max(n, m)) which can be simplified to O(max(n, m)).

Space Complexity

O(1) – The provided plain English explanation does not involve any auxiliary data structures like arrays, lists, or hash maps. The algorithm only compares string lengths and potentially iterates through the strings using index variables. Since the amount of extra memory used does not depend on the input string lengths, the space complexity is constant.

Optimal Solution

Approach

The problem asks for the length of the longest string if it is not a subsequence of the other. The trick is to realize there are only a few possibilities we need to check instead of trying every subsequence combination. We can use some clever comparisons.

Here's how the algorithm would work step-by-step:

First, check if the two strings are exactly the same. If they are, there is no uncommon subsequence, so the answer is zero.
If the strings are different, then the longer string (if one exists) is definitely an uncommon subsequence.
If the strings have the same length and are different, then either one of them is an uncommon subsequence, so we return the length of either one.

Code Implementation

def longest_uncommon_subsequence(first_string, second_string):
    # If strings are identical, there's no uncommon subsequence.
    if first_string == second_string:
        return 0

    # If one string is longer, it's an uncommon subsequence of the other.
    if len(first_string) != len(second_string):
        return max(len(first_string), len(second_string))

    # If strings have the same length but are different,
    # either one is an uncommon subsequence.
    return len(first_string)

Big(O) Analysis

Time Complexity

O(n) – The provided solution primarily involves string comparisons. First, we check if the two strings are equal, which takes O(n) time, where n is the length of the strings (assuming they are of comparable length or n is the length of the longer string). Then, we might compare the lengths of the strings, which is O(1). Finally, if they have different lengths, we can return the length of the longer string. If the lengths are the same, we return the length of either one. Since the string comparison dominates, the overall time complexity is O(n).

Space Complexity

O(1) – The described solution only uses a constant amount of extra space. It primarily involves comparing the lengths and contents of the input strings, without allocating any auxiliary data structures that scale with the input size (N), where N represents the length of the strings. The comparisons and length checks are done in place, meaning they don't require additional memory proportional to the input. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Both strings are null or empty	Return -1 as no subsequence can be formed.
One string is null or empty, the other is not	Return the length of the non-null/empty string as it is a subsequence of itself but not of the null/empty string.
Strings are identical	Return -1 because neither string is a subsequence of the other and therefore no uncommon subsequence exists.
One string is a subsequence of the other	Return the length of the longer string, which is the uncommon subsequence.
Strings are of different lengths and share a common prefix/suffix	A simple length comparison suffices, as the longer string contains the uncommon subsequence.
Maximum string length is reached	Ensure the algorithm doesn't lead to integer overflows when calculating lengths and that memory usage is reasonable; length comparison is O(1).
Strings contain non-ASCII characters	The length function should correctly handle UTF-8 or other encodings without errors.
Strings contain only whitespace characters	The whitespace will be included in the length calculation and handled the same as other characters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings be empty or null?
What is the maximum length of the input strings?
Are the input strings case-sensitive (i.e., should 'abc' and 'Abc' be considered different)?
If no uncommon subsequence exists, what should the function return?
Are there any special characters or encoding considerations within the strings?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if the words are completely different. If they are, the longer word is the answer.
If the words are the same, there's no uncommon subsequence, so the answer is that there isn't one.
If the words are not completely different, then check if the first word is a special part of the second word. This means, can you make the first word by picking letters out of the second word, in the same order?
Also check the other way, is the second word a special part of the first word?
If neither word is a special part of the other, then the longer word is the answer.
If one word is a special part of the other, then the word that is not a special part is the answer. The algorithm must return the longest length possible given those criteria.

Code Implementation

def find_longest_uncommon_subsequence_length(first_string, second_string):
    # Check if the strings are identical
    if first_string == second_string:
        return -1

    first_string_length = len(first_string)
    second_string_length = len(second_string)

    # Determine if one string is a subsequence of the other
    if is_subsequence(first_string, second_string):
        return second_string_length

    # Determine if one string is a subsequence of the other
    if is_subsequence(second_string, first_string):
        return first_string_length

    # If neither is a subsequence of the other, return the length of the longer string
    return max(first_string_length, second_string_length)

def is_subsequence(shorter_string, longer_string):
    shorter_string_index = 0
    longer_string_index = 0

    while shorter_string_index < len(shorter_string) and longer_string_index < len(longer_string):
        if shorter_string[shorter_string_index] == longer_string[longer_string_index]:
            shorter_string_index += 1

        longer_string_index += 1

    # Check if all characters of shorter_string were found in longer_string
    return shorter_string_index == len(shorter_string)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if the two strings are exactly the same. If they are, there is no uncommon subsequence, so the answer is zero.
If the strings are different, then the longer string (if one exists) is definitely an uncommon subsequence.
If the strings have the same length and are different, then either one of them is an uncommon subsequence, so we return the length of either one.

Code Implementation

def longest_uncommon_subsequence(first_string, second_string):
    # If strings are identical, there's no uncommon subsequence.
    if first_string == second_string:
        return 0

    # If one string is longer, it's an uncommon subsequence of the other.
    if len(first_string) != len(second_string):
        return max(len(first_string), len(second_string))

    # If strings have the same length but are different,
    # either one is an uncommon subsequence.
    return len(first_string)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both strings are null or empty	Return -1 as no subsequence can be formed.
One string is null or empty, the other is not	Return the length of the non-null/empty string as it is a subsequence of itself but not of the null/empty string.
Strings are identical	Return -1 because neither string is a subsequence of the other and therefore no uncommon subsequence exists.
One string is a subsequence of the other	Return the length of the longer string, which is the uncommon subsequence.
Strings are of different lengths and share a common prefix/suffix	A simple length comparison suffices, as the longer string contains the uncommon subsequence.
Maximum string length is reached	Ensure the algorithm doesn't lead to integer overflows when calculating lengths and that memory usage is reasonable; length comparison is O(1).
Strings contain non-ASCII characters	The length function should correctly handle UTF-8 or other encodings without errors.
Strings contain only whitespace characters	The whitespace will be included in the length calculation and handled the same as other characters.