EasyStringMathRecursion

Greatest Common Divisor of Strings

1 approach, code in all languages

Say a string t divides a string s when s can be built by writing t some whole number of times back to back (for example, "ab" divides "ababab").

Given two strings str1 and str2, return the longest string x that divides both of them. If there is no such non-empty string, return an empty string.

Example 1

Input: str1 = "ABABAB", str2 = "ABAB"

Output: "AB"

"AB" repeated forms both inputs, and no longer common block exists.

Example 2

Input: str1 = "LEET", str2 = "CODE"

Output: ""

The two strings share no repeating block, so the answer is empty.

Constraints

1 ≤ str1.length ≤ 10^3
1 ≤ str2.length ≤ 10^3
str1 and str2 consist of uppercase English letters only

Concatenation check plus Euclidean gcd of lengths

If both concatenation orders match, the answer is the prefix whose length is the gcd of the two lengths.

Loading animation…

Intuition

If some string divides both inputs, then both are made of the same repeated block, which forces str1 + str2 to equal str2 + str1 regardless of order. When that holds, any common divisor's length must divide both lengths, and the largest such length is exactly their greatest common divisor, so the prefix of str1 of that length is the answer.

Algorithm walkthrough

1Compare str1 + str2 against str2 + str1; if they differ, no common divisor exists, so return an empty string.
2Otherwise the answer length equals gcd(len(str1), len(str2)).
3Compute the gcd recursively with the Euclidean rule gcd(a, b) = gcd(b, a mod b), stopping when b is 0.
4Return the prefix of str1 with that length.

Implementation

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""

        def gcd(a: int, b: int) -> int:
            if b == 0:
                return a
            return gcd(b, a % b)

        return str1[: gcd(len(str1), len(str2))]

Time

O(m + n)

Space

O(m + n)

m and n are the string lengths; building the two concatenations dominates the cost.

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI