Longest Shared Repeating Block

Easy

Say a string t **generates** a string s if s is t written one or more times in a row: s = t + t + … + t. Given strings first and second, return the longest string that generates both of them. If there is none, return the empty string.

Example 1

first='XYXYXYXY', second='XYXY' → 'XYXY'

Both strings are built from XYXY (twice and once), and no longer block works.

Example 2

first='KKKKKK', second='KKKK' → 'KK'

KK repeats 3 and 2 times; KKKK fails because six letters cannot be built from it.

Example 3

first='ABA', second='AB' → ''

There is no common block, so the answer is the empty string.

Constraints

1 ≤ len(first), len(second) ≤ 1000
Both strings consist of uppercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math String

Similar problems

Value of a Roman Numeral Easy Sum of Binary Strings Easy Spreadsheet Column Label Easy Spreadsheet Column Index Easy Counting Off by Threes and Fives Easy

Input

first='XYXYXYXY', second='XYXY'

Expected

'XYXY'

Run checks the first 3 tests in your browser. Submit checks all 175 tests on the server, hidden ones included.