GCD of Strings

Problem

Given two strings, return the largest string x such that x divides both str1 and str2, where x divides a string when the string is x repeated some number of times.

If str1 + str2 differs from str2 + str1 the answer is the empty string. Otherwise the common divisor must have length gcd(len(str1), len(str2)), so return that prefix.

Hint

If a common divisor exists, both strings are repetitions of the same block.

Test cases

case 1

in: ["ABCABC","ABC"]

expected: "ABC"

case 2

in: ["ABABAB","ABAB"]

expected: "AB"

case 3

in: ["LEET","CODE"]

expected: ""

case 4

in: ["",""]

expected: ""

case 5

in: ["A","A"]

expected: "A"

case 6

in: ["ABC","ABCABC"]

expected: "ABC"

Starter codePython

def gcd_of_strings(str1, str2):
    # Your code here
    pass

6 test cases · run your code against them in the editor