Show problems as
Classic problem #459EasyStringString MatchingZ AlgorithmKnuth–Morris–Pratt Algorithm

Repeated Substring Pattern

Real-world version: Ribbon Repeats a Motif
Tracked in this browser only
Read Repeated Substring Pattern on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A printed ribbon is described by the lowercase string s, one letter per printed cell, read from the left end to the right end.

Call the ribbon patterned when there is a block of cells strictly shorter than the whole ribbon such that laying that block down twice or more, end to end and always in the same direction, reproduces s exactly. Return true when the ribbon is patterned and false when it is not.

Examples

Example 1

Input
s = "abcabcabc"
Output
true

The block abc is shorter than the ribbon, and laying it down three times spells out the ribbon exactly, so the answer is true.

Example 2

Input
s = "aab"
Output
false

A block would have to divide the length of 3, so the only candidate shorter than the ribbon has length 1. Neither a nor b repeated three times spells aab, so the answer is false.

Example 3

Input
s = "abaababaab"
Output
true

The block abaab laid down twice spells abaababaab, which is the ribbon, so the answer is true.

Constraints

  • 1 <= s.length <= 10^4
  • s consists of lowercase English letters.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def repeated_substring_pattern(s: str) -> bool:
Java
public boolean repeatedSubstringPattern(String s)

More on the same topics