All Long Subsequences Are Dictionary Words
Updated
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:
answer[0]is true exactly when every considered subsequence appears in the dictionary.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 <= 180 <= dictionary.length <= 200000textand 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 Onsite Interview questions
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
- Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Numeric Poker OperationsRippling · PHONE SCREENRippling interview questions
- Generate Palindromic PermutationsMotive · ONSITE INTERVIEWMotive interview questions
- Maximum Unique Substring SplitThe Walt Disney Company · PHONE SCREENThe Walt Disney Company interview questions
- Word Pattern II (Round 1, LC 291 :)Microsoft · ONSITE INTERVIEWMicrosoft interview questions
- Word Break IIAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Word Break IIWex · PHONE SCREEN
- Word Break IIBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Longest Substring Without Repeating CharactersSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Business Account KYC Verification — Parts 1–5Stripe · PHONE SCREENStripe interview questions
- Classify Password StrengthHackerRank · PHONE SCREEN · ONSITE INTERVIEWHackerRank interview questions