DSA problem
Greatest Common Divisor of Strings
For two strings s and t, we say t divides s if s = t + t + ... + t for some positive integer number of repetitions. Given two strings str1 and str2, return the largest string x that divides both str1 and str2. If no such string exists, return an empty string.
The crucial observation is that a common-divisor string exists if and only if the two inputs can be expressed using the same repeating block. The cleanest way to test that condition is to check whether str1 + str2 == str2 + str1. If those two concatenations are equal, the strings share a common period; if they are not, no common-divisor string can exist and the answer is the empty string.
Once we know a common divisor exists, its length must divide both len(str1) and len(str2). By the same arithmetic reasoning that gives the greatest common divisor of two integers, the longest common-divisor string has length equal to gcd(len(str1), len(str2)). So the answer is simply the first gcd(m, n) characters of either input.
This approach is O(m + n) time dominated by the two string concatenations and the equality check; the Euclidean gcd of two lengths is O(log min(m, n)) and negligible. Memory is O(m + n) for the temporary concatenated strings.
Examples
str1 = "ABCABC", str2 = "ABC""ABC"str1 = "ABABAB", str2 = "ABAB""AB"str1 = "LEET", str2 = "CODE"""Constraints
- 1 <= str1.length, str2.length <= 1000
- str1 and str2 consist of English uppercase letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.