Scale Engineer

Longest Uncommon Subsequence I

Easy
#0506Time: 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: 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.
Data structures
String

Prompt

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:

-1

 

Constraints:

  • 1 <= a.length, b.length <= 100
  • a and b consist of lower-case English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem