This approach takes advantage of the fact that if two strings are identical, there are no uncommon subsequences. If they are different, the longest uncommon subsequence is the longest string itself.
a is equal to b, return -1 because all subsequences of a are subsequences of b and vice versa.a is not equal to b, return the maximum length of a or b since the longer string itself cannot be a subsequence of the other.Time Complexity: O(n) where n is the length of the strings, due to the string comparison.
Space Complexity: O(1), no additional space is needed.
1using System;
2
3class Program {
4 public static int FindLUSlength(string a, string b) {
5 return a == b ? -1 : Math.Max(a.Length, b.Length);
6 }
7
8 static void Main() {
9 string a = "aba";
10 string b = "cdc";
11 Console.WriteLine(FindLUSlength(a, b));
12 }
13}This C# solution uses the equality operator == for strings and Math.Max to calculate the desired result.
Another approach is to analyze the problem by considering the entire strings as potential subsequences and determine their existence in the other string.
Time Complexity: O(n + m) where n and m are the lengths of the strings.
Space Complexity: O(1), since no additional structures are employed.
1#include <iostream>
2#include <string>
3
4bool isSubsequence(std::string s, std::string t) {
5 int i = 0, j = 0;
6 while (i < s.size() && j < t.size()) {
7 if (s[i] == t[j]) i++;
8 j++;
9 }
10 return i == s.size();
11}
12
13int findLUSlength(std::string a, std::string b) {
14 if (isSubsequence(a, b) || isSubsequence(b, a)) return -1;
15 return std::max(a.size(), b.size());
16}
17
18int main() {
19 std::string a = "aba";
20 std::string b = "cdc";
21 std::cout << findLUSlength(a, b) << std::endl;
22 return 0;
23}The C++ solution also uses a helper function isSubsequence to check if one string is a subsequence of the other. Main logic applies this helper function to both a and b.