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.

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" }`.

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.

Read the full Google Software Engineer interview experience this question came from

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

  1. Two strings are anagrams exactly when their 26-letter frequency counts are the same.
  2. Group dictionary words by length, then use a sliding window over `s` for each possible substring length to compare frequency signatures efficiently.

Loading coding console...