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

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a string `s` (letters only) and access to an English dictionary `dict` (a set of valid words). Return `true` if **every contiguous substring** of `s` with length **>= 3** is a valid dictionary word (i.e., for all `i, j` with `0 <= i <= j < n` and `j - i + 1 >= 3`, `s[i..j] ∈ dict`). Otherwise return `false`. Clarifications: - Substring means **contiguous**. - You may assume dictionary lookups are available (e.g., `dict.contains(word)`), or you can preprocess the dictionary. Example: - If `s = "cats"`, you must check `"cat"`, `"ats"`, and `"cats"` (and any other substrings of length >= 3).

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

Part 1: Check Whether Every Subsequence of Length >= 3 Is 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 appears in the dictionary. A subsequence keeps the original character order but does not need to be contiguous. 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: ('cat', ['cat'])

Expected Output: True

Explanation: The only subsequence of length >= 3 is 'cat', which is in the dictionary.

Input: ('cats', ['cat', 'cas', 'cts', 'ats', 'cats'])

Expected Output: True

Explanation: All distinct subsequences of length >= 3 are: 'cat', 'cas', 'cts', 'ats', and 'cats'. All are present.

Input: ('cats', ['cat', 'cts', 'ats', 'cats'])

Expected Output: False

Explanation: The subsequence 'cas' is missing from the dictionary.

Input: ('', [])

Expected Output: True

Explanation: There are no subsequences of length >= 3, so the condition is vacuously true.

Input: ('aaaa', ['aaa', 'aaaa'])

Expected Output: True

Explanation: The distinct subsequences of length >= 3 are 'aaa' and 'aaaa', and both are in the dictionary.

Hints

Because len(s) is small, a DFS/backtracking solution that generates subsequences is feasible.
Repeated characters can create duplicate subsequences. A local set at each recursion depth can help avoid exploring duplicate branches.

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

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