Show problems as
Classic problem #1071EasyMathStringEuclidean AlgorithmGreatest Common Divisor

Greatest Common Divisor of Strings

Real-world version: Longest Shared Ribbon Tile
Tracked in this browser only
Read Greatest Common Divisor of Strings on LeetCode(opens in a new tab)

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

Learn the pattern firstBasic Recursive Functions · Recursion, animated step by step

A weaving shop records a ribbon as a string of uppercase letters, one letter per stitched panel.

A pattern x tiles a pattern y when laying out some whole number of copies of x back to back reproduces y letter for letter. So RG tiles RGRG and RGRGRG, and every pattern tiles itself.

You are given ribbons ribbonA and ribbonB. Return the longest pattern that tiles both of them. If no pattern tiles both, return the empty string. Whenever such a pattern exists there is exactly one longest one, so the answer is never ambiguous.

Examples

Example 1

Input
ribbonA = "RGBRGB", ribbonB = "RGBRGBRGB"
Output
"RGB"

Two copies of `RGB` give `ribbonA` and three copies give `ribbonB`. Laying `RGBRGB` or `RGBRGBRGB` end to end does not reproduce both ribbons.

Example 2

Input
ribbonA = "PQPQPQPQ", ribbonB = "PQPQ"
Output
"PQPQ"

Two copies of `PQPQ` give `ribbonA`, and one copy is `ribbonB` itself.

Example 3

Input
ribbonA = "MNM", ribbonB = "MN"
Output
""

Laying `M`, `N`, `MN` or `MNM` end to end never reproduces both ribbons, so there is no shared tile and the answer is the empty string.

Example 4

Input
ribbonA = "TTTT", ribbonB = "TT"
Output
"TT"

Two copies of `TT` give `ribbonA` and one copy is `ribbonB`.

Example 5

Input
ribbonA = "XYXY", ribbonB = "XYX"
Output
""

Laying `X`, `Y`, `XY`, `XYX` or `XYXY` end to end never reproduces both ribbons, so the answer is the empty string.

Constraints

  • 1 <= ribbonA.length, ribbonB.length <= 1000
  • ribbonA and ribbonB consist of uppercase English letters only.

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 gcd_of_strings(ribbonA: str, ribbonB: str) -> str:
Java
public String gcdOfStrings(String ribbonA, String ribbonB)

More on the same topics