522. Longest Uncommon Subsequence II

// LeetCode URL: https://leetcode.com/problems/longest-uncommon-subsequence-ii/
import java.util.Arrays;

/**
 * Sorting + Checking isSubsequence
 *
 * Time Complexity: Sort = O(N log N). each isSubsequence call takes O(X). Thus
 * total conplexity = O(N log N + N^2 * X) = O(N^2 * X)
 *
 * Space Complexity: O(1)
 *
 * N = Number of strings in strs array. X = average length of the strings.
 */
class Solution {
    public int findLUSlength(String[] strs) {
        if (strs == null || strs.length == 0) {
            return -1;
        }
        if (strs.length == 1) {
            return strs[0].length();
        }

        Arrays.sort(strs, (a, b) -> (b.length() - a.length()));

        for (int i = 0; i < strs.length; i++) {
            boolean flag = false;
            for (int j = 0; j < strs.length; j++) {
                if (strs[i].length() > strs[j].length()) {
                    break;
                }
                if (i == j) {
                    continue;
                }
                if (isSubsequence(strs[i], strs[j])) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                return strs[i].length();
            }
        }

        return -1;
    }

    private boolean isSubsequence(String s, String t) {
        int indexS = 0;
        for (int indexT = 0; indexT < t.length(); indexT++) {
            if (s.charAt(indexS) == t.charAt(indexT)) {
                indexS++;
            }
            if (indexS == s.length()) {
                return true;
            }
        }
        return false;
    }
}