algoadvance

Leetcode 521. Longest Uncommon Subsequence I

Problem Statement

Given two strings a and b, return the length of the longest uncommon subsequence between them. If the longest uncommon subsequence doesn’t exist, return -1.

An uncommon subsequence is a subsequence that is a substring of one of the strings but not a substring of the other.

Clarifying Questions

  1. What are the constraints on the length of a and b?
    • The length of both strings a and b will be between 1 and 100 inclusive.
  2. Can a and b be the same?
    • Yes, a and b can be the same string.
  3. What should be returned if the strings a and b are equal?
    • If a and b are equal, return -1 because there will be no uncommon subsequence.

Strategy

  1. Check if the strings a and b are equal.
    • If a == b, return -1 because there’s no uncommon subsequence.
  2. If a and b are not equal, the longest uncommon subsequence would simply be the longer string itself.
    • If the two strings are different, the entire string a (or b) cannot be a subsequence of the other string unless they are identical, which we already checked for.

Time Complexity

C++ Code Implementation

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

int findLUSlength(std::string a, std::string b) {
    if (a == b)
        return -1;
    return std::max(a.length(), b.length());
}

int main() {
    std::string a = "abc";
    std::string b = "cdc";
    std::cout << findLUSlength(a, b) << std::endl; // Output: 3

    a = "aaa";
    b = "bbb";
    std::cout << findLUSlength(a, b) << std::endl; // Output: 3

    a = "abc";
    b = "abc";
    std::cout << findLUSlength(a, b) << std::endl; // Output: -1

    return 0;
}

In the provided code, the findLUSlength function implements the strategy described. It first checks if the two strings are equal and returns -1 if they are. If they are not equal, it returns the length of the longer string, which is the length of the longest uncommon subsequence.

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