Check if all substrings are anagrams of 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** can be **rearranged (anagrammed)** into a valid dictionary word.
Formally, for every substring `t = s[i..j]` with `|t| >= 3`, there exists some word `w ∈ dict` such that `w` is a permutation of `t` (same multiset of characters). Otherwise return `false`.
Clarifications:
- Substring means **contiguous**.
- “Can be rearranged into a word” means the substring and the dictionary word have exactly the same character counts.
Example:
- If `t = "act"`, it passes if the dictionary contains any of `{ "act", "cat", "tac" }`.
Quick Answer: This question evaluates string-processing skills and combinatorial reasoning about character multisets, specifically anagram recognition, substring enumeration, and the use of efficient representations for repeated checks.
You are given a lowercase string `s` and a list `words` representing a dictionary of valid English words.
Return `True` if every contiguous substring of `s` with length at least 3 can be rearranged into at least one dictionary word. Otherwise, return `False`.
Two strings are anagrams if they contain exactly the same characters with the same frequencies.
Notes:
- A substring must be contiguous.
- If `len(s) < 3`, there are no substrings to check, so the answer is `True`.
- Dictionary words shorter than 3 are irrelevant for this task.
Constraints
- 0 <= len(s) <= 300
- 0 <= len(words) <= 5000
- s and every word in words contain only lowercase English letters 'a' to 'z'
- The total number of characters across all dictionary words is at most 200000
Examples
Input: ("act", ["cat", "dog"])
Expected Output: True
Explanation: The only substring of length at least 3 is "act", which is an anagram of "cat".
Input: ("abca", ["cab", "abca", "zzz"])
Expected Output: True
Explanation: Length-3 substrings are "abc" and "bca", both anagrams of "cab". The full substring "abca" is already in the dictionary.
Hints
- Two strings are anagrams exactly when their 26-letter frequency counts are the same.
- Group dictionary words by length, then use a sliding window over `s` for each possible substring length to compare frequency signatures efficiently.