Longest Uncommon Subsequence I - Practice Coding Problems

Longest Uncommon Subsequence I - Problem

String Easy

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.

Input & Output

Example 1 — Different Strings

$ Input: a = "aba", b = "cdc"

› Output: 3

💡 Note: Since "aba" ≠ "cdc", each string is a subsequence of itself but not the other. The longest uncommon subsequence is the entire string "aba" or "cdc", both with length 3.

Example 2 — Identical Strings

$ Input: a = "aaa", b = "aaa"

› Output: -1

💡 Note: Since both strings are identical, any subsequence of one will also be a subsequence of the other. No uncommon subsequence exists.

Example 3 — Different Lengths

$ Input: a = "abc", b = "defgh"

› Output: 5

💡 Note: The strings are different, so each is uncommon to the other. The longer string "defgh" has length 5, which is the answer.

Constraints

1 ≤ a.length, b.length ≤ 100
a and b consist of lower-case English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings a and b

Analysis

Check if strings are different

Output

Length of longest uncommon subsequence

Key Takeaway

🎯 Key Insight: Different strings are automatically uncommon subsequences of each other

Asked in

G Google 15 a Amazon 8

The key insight is that if two strings are different, each entire string is a subsequence of itself but not the other, making it uncommon. Best approach is direct comparison: return max length if different, -1 if identical. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Subsequences	O(2^n)	O(2^n)	Generate all subsequences and find longest uncommon one
Logical Analysis - Direct Comparison	O(1)	O(1)	Use logical reasoning instead of generating subsequences

Brute Force - Generate All Subsequences — Algorithm Steps

Generate all subsequences of string a
Generate all subsequences of string b
Find subsequences that exist in exactly one string
Return length of longest uncommon subsequence

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 2^n subsequences for each string

Compare

Find subsequences in exactly one set

Maximum

Return length of longest uncommon subsequence

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_SUBSEQ 1000

typedef struct {
    char subseq[100][50];
    int count;
} SubseqSet;

bool contains(SubseqSet* set, const char* seq) {
    for (int i = 0; i < set->count; i++) {
        if (strcmp(set->subseq[i], seq) == 0) return true;
    }
    return false;
}

SubseqSet getSubsequences(const char* s) {
    SubseqSet result;
    result.count = 0;
    int n = strlen(s);
    
    for (int mask = 0; mask < (1 << n); mask++) {
        char subseq[50] = "";
        int pos = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subseq[pos++] = s[i];
            }
        }
        subseq[pos] = '\0';
        
        if (!contains(&result, subseq)) {
            strcpy(result.subseq[result.count], subseq);
            result.count++;
        }
    }
    return result;
}

int solution(const char* a, const char* b) {
    SubseqSet subseqA = getSubsequences(a);
    SubseqSet subseqB = getSubsequences(b);
    
    int maxLen = -1;
    
    for (int i = 0; i < subseqA.count; i++) {
        if (!contains(&subseqB, subseqA.subseq[i])) {
            int len = strlen(subseqA.subseq[i]);
            if (len > maxLen) maxLen = len;
        }
    }
    
    for (int i = 0; i < subseqB.count; i++) {
        if (!contains(&subseqA, subseqB.subseq[i])) {
            int len = strlen(subseqB.subseq[i]);
            if (len > maxLen) maxLen = len;
        }
    }
    
    return maxLen;
}

int main() {
    char a[100], b[100];
    fgets(a, sizeof(a), stdin);
    fgets(b, sizeof(b), stdin);
    a[strcspn(a, "\n")] = 0;
    b[strcspn(b, "\n")] = 0;
    
    int result = solution(a, b);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Generate 2^n subsequences for each string of length n

⚠ Quadratic Growth

Space Complexity

O(2^n)

Store all generated subsequences

⚠ Quadratic Space

25.0K Views

Medium Frequency

~5 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler