algoadvance

Leetcode 522. Longest Uncommon Subsequence II

Problem Statement

Given a list of strings, you need to find the longest string that is an uncommon subsequence among the given strings. An uncommon subsequence is a string that is a subsequence of one string but not of any other string. If no such string exists, return -1.

A subsequence is a sequence derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Clarifying Questions

• Input: What is the range of the length and quantity of strings?
  • The input consists of a list of strings strs.
• Output: What should be returned if multiple uncommon subsequences of the same maximum length exist?
  • Only the length of the longest one is relevant. We don’t need to identify all sequences, only the length of the longest.
• Edge Cases: How to deal with strings that are identical?
  • Identical strings cannot have an uncommon subsequence among themselves if they are the only strings in the list and are the longest.

Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool isSubsequence(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] == b[j]) {
            i++;
        }
        j++;
    }
    return i == n;
}

int findLUSlength(vector<string>& strs) {
    sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
        return a.size() > b.size();
    });

    for (int i = 0; i < strs.size(); ++i) {
        bool isUncommon = true;
        for (int j = 0; j < strs.size(); ++j) {
            if (i != j && isSubsequence(strs[i], strs[j])) {
                isUncommon = false;
                break;
            }
        }
        if (isUncommon) {
            return strs[i].size();
        }
    }
    return -1;
}

int main() {
    vector<string> strs = {"aba", "cdc", "eae"};
    cout << findLUSlength(strs) << endl;
    return 0;
}

Strategy

1. Sorting: Sort the strings by length in descending order. This allows us to check longer strings first, which could potentially be our answer due to their length.
2. Subsequence Checking: For each string, check if it is a subsequence of any other string longer or equal in length.
3. IsUncommon Calculation: If a string is not a subsequence of any other string, it is an uncommon subsequence.
4. Early Return: Return the length of the first uncommon subsequence found during iteration.
5. Edge Handling: If no such uncommon subsequence exists among the input strings, return -1.

Time Complexity

• Sorting: O(n log n), where n is the number of strings.
• Subsequence Checking: For each string, checking against all other strings is O(m^2 * l), where m is the number of strings and l is the maximum length of the strings.
• Overall: The complexity is dominated by the subsequence checking, resulting in O(n^2 * l).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?