Welcome to Subscribe On Youtube

522. Longest Uncommon Subsequence II

Description

Given an array of strings strs, return the length of the longest uncommon subsequence between them. If the longest uncommon subsequence does not exist, return -1.

An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.

A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.

• For example, "abc" is a subsequence of "aebdc" because you can delete the underlined characters in "aebdc" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).

 

Example 1:

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

Example 2:

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

 

Constraints:

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

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public int findLUSlength(String[] strs) {
          int ans = -1;
          for (int i = 0, j = 0, n = strs.length; i < n; ++i) {
              for (j = 0; j < n; ++j) {
                  if (i == j) {
                      continue;
                  }
                  if (check(strs[j], strs[i])) {
                      break;
                  }
              }
              if (j == n) {
                  ans = Math.max(ans, strs[i].length());
              }
          }
          return ans;
      }
  
      private boolean check(String a, String b) {
          int j = 0;
          for (int i = 0; i < a.length() && j < b.length(); ++i) {
              if (a.charAt(i) == b.charAt(j)) {
                  ++j;
              }
          }
          return j == b.length();
      }
  }
  

• class Solution {
  public:
      int findLUSlength(vector<string>& strs) {
          int ans = -1;
          for (int i = 0, j = 0, n = strs.size(); i < n; ++i) {
              for (j = 0; j < n; ++j) {
                  if (i == j) continue;
                  if (check(strs[j], strs[i])) break;
              }
              if (j == n) ans = max(ans, (int) strs[i].size());
          }
          return ans;
      }
  
      bool check(string a, string b) {
          int j = 0;
          for (int i = 0; i < a.size() && j < b.size(); ++i)
              if (a[i] == b[j]) ++j;
          return j == b.size();
      }
  };
  

• class Solution:
      def findLUSlength(self, strs: List[str]) -> int:
          def check(a, b):
              i = j = 0
              while i < len(a) and j < len(b):
                  if a[i] == b[j]:
                      j += 1
                  i += 1
              return j == len(b)
  
          n = len(strs)
          ans = -1
  
          for i in range(n):
              j = 0
              while j < n:
                  if i == j or not check(strs[j], strs[i]):
                      j += 1
                  else:
                      break
              if j == n:
                  ans = max(ans, len(strs[i]))
          return ans
  
  

• func findLUSlength(strs []string) int {
  	check := func(a, b string) bool {
  		j := 0
  		for i := 0; i < len(a) && j < len(b); i++ {
  			if a[i] == b[j] {
  				j++
  			}
  		}
  		return j == len(b)
  	}
  
  	ans := -1
  	for i, j, n := 0, 0, len(strs); i < n; i++ {
  		for j = 0; j < n; j++ {
  			if i == j {
  				continue
  			}
  			if check(strs[j], strs[i]) {
  				break
  			}
  		}
  		if j == n && ans < len(strs[i]) {
  			ans = len(strs[i])
  		}
  	}
  	return ans
  }
  

All Problems

All Solutions