Longest Uncommon Subsequence I

EASY

Description

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 lower-case English letters.

Approaches

Checkout 3 different approaches to solve Longest Uncommon Subsequence I. Click on different approaches to view the approach and algorithm in detail.

Brute Force by Generating All Subsequences

This approach involves generating every possible subsequence for both strings, a and b. We can store these subsequences in two separate sets to handle duplicates. Then, we iterate through each set and find a subsequence that does not exist in the other set. The length of the longest such subsequence is our answer.

Algorithm

Create two hash sets, setA and setB, to store the subsequences of strings a and b.
Implement a recursive helper function generateSubsequences(String s, int index, StringBuilder current, Set<String> set) to find all 2^n - 1 non-empty subsequences of s and add them to the given set.
Call this function for both a and b to populate setA and setB.
Initialize a variable maxLength to -1.
Iterate through each subsequence sub in setA. If sub is not present in setB, update maxLength = Math.max(maxLength, sub.length()).
Iterate through each subsequence sub in setB. If sub is not present in setA, update maxLength = Math.max(maxLength, sub.length()).
Return maxLength.

This method is a direct, albeit naive, translation of the problem's definition into code. It exhaustively generates all subsequences for both input strings and then compares the resulting sets of subsequences to find one that is unique to its original string. The longest such unique subsequence's length is the result.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findLUSlength(String a, String b) {
        Set<String> setA = new HashSet<>();
        generateSubsequences(a, 0, new StringBuilder(), setA);
        
        Set<String> setB = new HashSet<>();
        generateSubsequences(b, 0, new StringBuilder(), setB);
        
        int maxLength = -1;
        for (String s : setA) {
            if (!setB.contains(s)) {
                maxLength = Math.max(maxLength, s.length());
            }
        }
        
        for (String s : setB) {
            if (!setA.contains(s)) {
                maxLength = Math.max(maxLength, s.length());
            }
        }
        
        return maxLength;
    }

    private void generateSubsequences(String s, int index, StringBuilder current, Set<String> set) {
        if (index == s.length()) {
            if (current.length() > 0) {
                set.add(current.toString());
            }
            return;
        }
        
        // Case 1: Exclude the character at the current index
        generateSubsequences(s, index + 1, current, set);
        
        // Case 2: Include the character at the current index
        current.append(s.charAt(index));
        generateSubsequences(s, index + 1, current, set);
        current.deleteCharAt(current.length() - 1); // Backtrack
    }
}

Complexity Analysis

Time Complexity: O(L_a * 2^|a| + L_b * 2^|b|). Generating all subsequences for a string of length n takes exponential time. For each string, there are 2^n subsequences, and creating/hashing them takes time proportional to their lengths.Space Complexity: O(L_a * 2^|a| + L_b * 2^|b|), where |s| is the length of string s and L_s is the total length of all subsequences of s. This is because we need to store all 2^n subsequences for each string.

Pros and Cons

Pros:

It's a straightforward implementation based on the problem definition.
Guaranteed to be correct if it could run within time and memory limits.

Cons:

Extremely inefficient in both time and space.
Not feasible for the given constraints and will result in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error.

Code Solutions

Checking out 3 solutions in different languages for Longest Uncommon Subsequence I. Click on different languages to view the code.

class Solution {
public
  int findLUSlength(String a, String b) {
    return a.equals(b) ? -1 : Math.max(a.length(), b.length());
  }
}

Video Solution

Watch the video walkthrough for Longest Uncommon Subsequence I

Data Structures:

String