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 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.

Input: ("abcd", ["abc", "bcd"])

Expected Output: False

Explanation: The length-3 substrings pass, but the length-4 substring "abcd" has no dictionary anagram.

Input: ("abcb", ["abc", "bbca"])

Expected Output: False

Explanation: "abc" passes, and the full string "abcb" is an anagram of "bbca", but the substring "bcb" is not an anagram of any dictionary word.

Input: ("hi", [])

Expected Output: True

Explanation: There are no substrings of length at least 3, so the condition is vacuously true.

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

Expected Output: True

Explanation: Both length-3 substrings are "aaa", and the full substring is "aaaa". Duplicate dictionary words do not change the answer.

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.

Quick Overview

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.