Katkat
Back

Check if all substrings are anagrams of words

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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