EasyStringMathRecursion

Greatest Common Divisor of Strings

1 approach, code in every language

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 see the solution

You get 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

After the pattern

Now solve one you haven't seen.

Longest Shared Ribbon Tile is our own problem on the technique behind Greatest Common Divisor of Strings: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free