How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Check if all substrings are dictionary words

Quick Overview

This question evaluates string-processing skills such as substring enumeration and membership testing against a dictionary, along with algorithmic reasoning about correctness and complexity.

Loading coding console...

Part 2: Check Whether Every Subsequence of Length >= 3 Can Be Rearranged Into a Dictionary Word

Given a lowercase string s and a dictionary of valid words, return True if every distinct subsequence of s whose length is at least 3 can be rearranged to form some dictionary word. A subsequence keeps the original order but does not need to be contiguous. Rearranging means the subsequence and the dictionary word must contain exactly the same letters with the same counts. If s has length less than 3, return True. If the same subsequence string can be formed from multiple index choices, it only needs to be checked once.

Constraints

0 <= len(s) <= 18
0 <= len(dictionary) <= 3000
1 <= len(word) <= 18 for each word in dictionary
s and all dictionary words contain only lowercase English letters

Examples

Input: ('eat', ['tea'])

Expected Output: True

Explanation: The only subsequence of length >= 3 is 'eat', which can be rearranged into 'tea'.

Input: ('abcd', ['cba', 'dba', 'cad', 'dcb', 'dcba'])

Expected Output: True

Explanation: The subsequences 'abc', 'abd', 'acd', 'bcd', and 'abcd' all have matching anagram signatures in the dictionary.

Input: ('abcd', ['cba', 'dba', 'cad', 'dcba'])

Expected Output: False

Explanation: The subsequence 'bcd' has no matching anagram in the dictionary.

Input: ('ab', [])

Expected Output: True

Explanation: There are no subsequences of length >= 3, so the answer is True.

Input: ('aab', ['aba'])

Expected Output: True

Explanation: The only subsequence of length >= 3 is 'aab', and it can be rearranged into 'aba'.

Hints

Two strings can be rearranged into each other if their character-frequency counts are identical.
Precompute a signature for each dictionary word, and maintain the current subsequence's frequency counts incrementally during DFS.

Quick Overview