FastPrepAll Long Subsequences Are Dictionary Words
Problem · String

All Long Subsequences Are Dictionary Words

Learn this problem
● MediumGoogle logoGoogleNEW GRADONSITE INTERVIEW
See Google hiring insights

Problem statement

Given a lowercase string text and a finite lowercase dictionary, consider every subsequence of text whose length is at least 3. A subsequence keeps relative order and is identified by its resulting string; repeated ways to form the same string do not change the decision.

Return two booleans:

  1. answer[0] is true exactly when every considered subsequence appears in the dictionary.
  2. answer[1] is true exactly when, for every considered subsequence, at least one dictionary word is an anagram of it.

If text.length < 3, both statements are vacuously true. Duplicate dictionary entries have no effect.

Function

allSubsequencesAreWords(text: String, dictionary: String[]) → boolean[]

Examples

Example 1

text = "abc"dictionary = ["abc","cab"]return = [true,true]

The only qualifying subsequence is abc. It is present directly and also has dictionary anagrams.

Example 2

text = "abc"dictionary = ["bca"]return = [false,true]

The subsequence abc is not itself in the dictionary, but bca is an anagram of it.

Example 3

text = "abcd"dictionary = ["abc","abd","acd","bcd","abcd"]return = [true,true]

The four length-three subsequences and the full length-four subsequence all appear directly, so both conditions hold.

Constraints

  • 0 <= text.length <= 18
  • 0 <= dictionary.length <= 200000
  • text and every dictionary word contain only lowercase English letters.
  • Each dictionary word has length at most 18.
  • The total number of dictionary characters is at most 1000000.

More Google problems

drafts saved locally
public boolean[] allSubsequencesAreWords(String text, String[] dictionary) {
    // Write your code here.
}
text"abc"
dictionary["abc","cab"]
expected[true,true]
checking account