Greatest Common Divisor of Strings

Given two strings str1 and str2, return the largest string x that divides both strings. A string x divides a string s if s can be formed by concatenating x one or more times.

Input Format

str1 and str2 = strings

Output Format

largest common divisor string

Constraints

  • 1 <= str1.length, str2.length <= 1000

Examples

Example 1:

Input:

str1 = "ABCABC"
str2 = "ABC"

Output:

ABC

Explanation:

ABC repeats to form both strings.

Example 2:

Input:

str1 = "ABABAB"
str2 = "ABAB"

Output:

AB

Explanation:

AB is the greatest string that divides both.

Loading...
Greatest Common Divisor of Strings - Math