为美好的世界献上 code

522. Longest Subsequence II

522. Longest Uncommon Subsequence II#

Given a list of strings strs, return the length of the longest uncommon subsequence. If the longest uncommon subsequence does not exist, return -1.

A subsequence of a string s can be obtained by deleting some characters from s.

A special subsequence is a subsequence that is unique and cannot be a subsequence of any other string.

For example, "abc" is a subsequence of "aebdc", as you can delete the underscore characters in "aebdc" to obtain "abc". The subsequence of "aebdc" also includes "aebdc", "aeb", and "" (empty string).

Example 1:

Input: strs = ["aba","cdc","eae"]
Output: 3

Example 2:

Input: strs = ["aaa","aaa","aa"]
Output: -1


  • 2 <= strs.length <= 50
  • 1 <= strs[i].length <= 10
  • strs[i] consists of lowercase English letters


If strs = ["abc", "abcd", "abcde"], "abcd" is not a subsequence of "abc", but "abcd" is a subsequence of "abcde", and "abcde" is not a subsequence of "abcd" or "abc". Therefore, the longest uncommon subsequence we are looking for is "abcde".

Here is the implementation:

class Solution {
    int findLUSlength(vector<string>& strs) {
        // Check if str1 is a subsequence of str2
        auto isSub = [&](const string &str1, const string &str2) -> bool {
            int j = 0;
            for (int i = 0; i < str2.size(); ++i) {
                if (str1[j] == str2[i]) {
            return j == str1.size();

        int res = -1;
        for (int i = 0; i < strs.size(); ++i) {
            bool flag = true;
            // Only consider the length of the current string if it is greater than the length of the longest uncommon subsequence
            if (strs[i].size() > res) {
                for (int j = 0; j < strs.size(); ++j) {
                    if (j != i && isSub(strs[i], strs[j])) {
                        flag = false;
                if (flag) {
                    res = strs[i].size();

        return res;

This problem is actually not difficult, but it is easy to make mistakes. The above code actually has a bug.

The bug lies in the comparison of the length of the current string with the length of the longest uncommon subsequence if (strs[i].size() > res). The size() function returns a size_t type, which is an unsigned type, while res is a signed type. When comparing them, res is implicitly promoted to an unsigned type, and on a 64-bit operating system, the value of res becomes 264+12^{64}+1. In addition to this implicit conversion, there are multiple implicit conversion issues in the code.

Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.