Built From One Block

EasyTries & Strings

Problem

A tiling machine prints a string by stamping the same block two or more times in a row. Given s, return true if it could have been printed this way, i.e. s equals some shorter block repeated at least twice.

Example 1

Input:
s = "abab"
Output:
true

"ab" stamped twice.

Example 2

Input:
s = "aba"
Output:
false

Example 3

Input:
s = "xyzxyzxyz"
Output:
true

Constraints

  • 1 ≤ s.length ≤ 10^4
  • Lowercase English letters only.

Hint

Show the first hint

If s is a block repeated, what is true about s compared with itself shifted by the block length?

Walkthrough

How to approach it

01Clarify before coding

  • Must the block repeat at least twice? Yes; a string is not built from itself once.
  • Can the block be a single letter? Yes: "aa" is valid.

02Brute force

For every block length d that divides n and is below n, check whether s equals s[:d] repeated n/d times.

Cost: O(n·divisors(n)): fine in practice, but the prefix-function solution is cleaner and strictly linear.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.