Longest Uncommon Subsequence II - Practice Coding Problems

Longest Uncommon Subsequence II - Problem

Given an array of strings strs, return the length of the longest uncommon subsequence between them. If the longest uncommon subsequence does not exist, return -1.

An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.

A subsequence of a string s is a string that can be obtained after deleting any number of characters from s. For example, "abc" is a subsequence of "aebdc" because you can delete the underlined characters in "aebdc" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).

Input & Output

Example 1 — Mixed Unique and Duplicate

$ Input: strs = ["aba", "cdc", "eae", "eae"]

› Output: 3

💡 Note: "aba" and "cdc" are unique strings (appear only once). "eae" appears twice so it's not uncommon. The longest unique strings have length 3.

Example 2 — All Identical Strings

$ Input: strs = ["aaa", "aaa", "aa"]

› Output: 2

💡 Note: "aaa" appears twice, but "aa" is unique. The longest uncommon subsequence has length 2.

Example 3 — All Strings Are Identical

$ Input: strs = ["abc", "abc", "abc"]

› Output: -1

💡 Note: All strings are identical, so no string is unique. No uncommon subsequence exists.

Constraints

2 ≤ strs.length ≤ 50
1 ≤ strs[i].length ≤ 10
strs[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings: ["aba", "cdc", "eae", "eae"]

Process

Find strings that appear exactly once

Output

Length of longest unique string: 3

Key Takeaway

🎯 Key Insight: A string that appears only once is automatically an uncommon subsequence

Asked in

G Google 15 f Facebook 12

The key insight is that any string appearing exactly once in the array is automatically an uncommon subsequence of itself. Best approach uses a hash map to count frequencies in O(n) time. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Count Frequencies	O(n)	O(n)	Use a hash map to count string frequencies, then find the longest string with frequency 1
Brute Force - Check All Subsequences	O(n × 2^m × n × m)	O(2^m)	Generate all possible subsequences and check which ones are uncommon
Key Insight - Unique Strings	O(n²)	O(1)	Any string that appears only once is automatically an uncommon subsequence

Hash Map - Count Frequencies — Algorithm Steps

Count frequency of each string using hash map
Iterate through strings and check frequency
Return length of longest string with frequency 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Count

Build frequency map of all strings

Filter

Find strings with frequency = 1

Maximum

Return length of longest unique string

Code -

solution.c — C

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

typedef struct {
    char str[11];
    int count;
} StringCount;

int solution(char** strs, int strsSize) {
    StringCount freq[50];
    int freqSize = 0;
    
    // Count frequency of each string
    for (int i = 0; i < strsSize; i++) {
        bool found = false;
        for (int j = 0; j < freqSize; j++) {
            if (strcmp(freq[j].str, strs[i]) == 0) {
                freq[j].count++;
                found = true;
                break;
            }
        }
        if (!found) {
            strcpy(freq[freqSize].str, strs[i]);
            freq[freqSize].count = 1;
            freqSize++;
        }
    }
    
    int maxLen = -1;
    
    // Find longest string with frequency 1
    for (int i = 0; i < strsSize; i++) {
        for (int j = 0; j < freqSize; j++) {
            if (strcmp(freq[j].str, strs[i]) == 0 && freq[j].count == 1) {
                int len = strlen(strs[i]);
                if (len > maxLen) {
                    maxLen = len;
                }
                break;
            }
        }
    }
    
    return maxLen;
}

int main() {
    char line[10001];
    fgets(line, sizeof(line), stdin);
    
    char* strs[51];
    int strsSize = 0;
    
    char* token = strtok(line, "[],\"");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            strs[strsSize] = malloc(strlen(token) + 1);
            strcpy(strs[strsSize], token);
            strsSize++;
        }
        token = strtok(NULL, "[],\"");
    }
    
    int result = solution(strs, strsSize);
    printf("%d\n", result);
    
    for (int i = 0; i < strsSize; i++) {
        free(strs[i]);
    }
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the array: one to count, one to find maximum

✓ Linear Growth

Space Complexity

O(n)

Hash map stores at most n unique strings

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

856 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

Hash Map - Count Frequencies — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler