A Subsequence of One Word Only

Medium

You are given an array of strings words. A subsequence of a string is obtained by deleting any of its characters (possibly none) without reordering the rest. Call a string t private to the element words[i] if t is a subsequence of words[i] and of no other element of the array (duplicates count as separate elements). Return the greatest length of a string that is private to at least one element, or -1 if no such string exists.

Example 1

words=['cat', 'act', 'ca'] → 3

The string "act" is a subsequence of the word "act" alone: neither "cat" nor "ca" yields it. Its length is 3.

Example 2

words=['xyz', 'xyz', 'xy'] → -1

Everything obtainable from "xy" by deletions is also obtainable from "xyz", and the two "xyz" are identical. No word owns a subsequence of its own, so the answer is -1.

Constraints

2 ≤ words.length ≤ 500
1 ≤ words[i].length ≤ 10
words[i] consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Two Pointers String Sorting

Similar problems

Word Growth Chain Medium Anagram Buckets Medium Longest Word by Crossing Out Medium Pairs With a Fixed Gap Medium Most Searched Words Medium

Input

words=['cat', 'act', 'ca']

Expected

Run checks the first 3 tests in your browser. Submit checks all 101 tests on the server, hidden ones included.