Greatest Common Divisor of Strings: GCD Pattern

May 27, 20266 min read

leetcodeproblemeasystringsmath

LeetCode 1071, Greatest Common Divisor of Strings, defines string division like this: for two strings s and t, we say "t divides s" if s can be formed by concatenating t with itself one or more times. Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

For example, given str1 = "ABCABC" and str2 = "ABC", the answer is "ABC". The string "ABC" repeated twice gives str1, and repeated once gives str2. No longer string divides both.

Both str1 and str2 are built from the same repeating unit "ABC". The largest string that divides both is "ABC" itself.

Why this problem matters

This problem bridges two ideas that do not seem related at first: string manipulation and number theory. The connection between repeating string patterns and the mathematical GCD function is a beautiful insight. Once you see it, you realize that the structure of repeating strings mirrors the structure of divisibility in integers. A string that "divides" another string is analogous to an integer that divides another integer.

This pattern shows up whenever you need to find periodicity in sequences, detect repeating units, or reduce a problem about strings to a problem about lengths. Understanding the GCD-of-strings trick also strengthens your intuition for problems involving cyclic patterns, string rotations, and modular arithmetic on sequences.

The key insight

If a string x divides both str1 and str2, then str1 is just x repeated some number of times, and str2 is x repeated some other number of times. That means str1 + str2 and str2 + str1 must produce the same string, because both are just x repeated (a + b) times regardless of the order.

The converse is also true. If str1 + str2 does not equal str2 + str1, then no common divisor string exists and the answer is "".

Once you know a common divisor exists, the length of the greatest one must be gcd(len(str1), len(str2)). This follows from the same logic as integer GCD: the largest unit that evenly tiles both strings must have a length that divides both string lengths. The GCD of those lengths is exactly that largest divisor.

So the algorithm is:

Check if str1 + str2 == str2 + str1. If not, return "".
Compute g = gcd(len(str1), len(str2)).
Return str1[:g].

The solution

from math import gcd

def gcd_of_strings(str1: str, str2: str) -> str:
    if str1 + str2 != str2 + str1:
        return ""
    return str1[:gcd(len(str1), len(str2))]

Here is what each piece does:

The concatenation check str1 + str2 != str2 + str1 determines whether any common divisor string exists. If the two concatenation orders produce different results, the strings do not share a repeating base, and the answer is empty.
gcd(len(str1), len(str2)) computes the greatest common divisor of the two lengths. This gives the length of the longest possible divisor string.
str1[:g] extracts the first g characters of str1. Since we already know a divisor exists, this prefix is guaranteed to be the answer.

You do not need to verify that the candidate substring actually divides both strings. The concatenation check str1 + str2 == str2 + str1 is a necessary and sufficient condition. If it passes, the GCD-length prefix is always the correct answer.

Practice string patterns with spaced repetition

Visual walkthrough

Let's trace through str1 = "ABCABC" and str2 = "ABC" step by step. Watch how the concatenation test, the GCD computation, and the substring extraction work together to produce the answer.

Step 1: Check if a common divisor can exist

Concatenate in both orders: str1 + str2 = "ABCABCABC" and str2 + str1 = "ABCABCABC". They are equal, so a common divisor string exists. If they were not equal, the answer would be "".

Step 2: Compute the GCD of the lengths

len(str1) = 6 and len(str2) = 3. Compute gcd(6, 3) = 3. The GCD of the lengths tells us how long the candidate divisor string must be.

Step 3: Extract the candidate substring

Take the first gcd(6, 3) = 3 characters of str1: "ABC". This is the candidate that should divide both strings.

Step 4: Verify the candidate

"ABC" repeated 2 times = "ABCABC" = str1. "ABC" repeated 1 time = "ABC" = str2. The candidate divides both strings, confirming the answer.

Step 5: Return the result

The greatest common divisor of "ABCABC" and "ABC" is "ABC".

Since the concatenation check passed and the GCD-length prefix divides both strings, the answer is "ABC".

The entire solution runs in just a few operations. The concatenation check does the heavy lifting by confirming that a common structure exists. After that, the GCD computation and the slice are both constant-time (relative to the math involved).

Complexity analysis

Metric	Value
Time	O(m + n), where m and n are the lengths of str1 and str2
Space	O(m + n), for the concatenated strings

The concatenation check creates two new strings of length m + n and compares them character by character. The GCD computation on two integers runs in O(log(min(m, n))) time, which is negligible. The final slice is O(g) where g is the GCD, which is at most min(m, n). Overall, the concatenation dominates at O(m + n).

The building blocks

Concatenation order as a structural test

Checking whether str1 + str2 == str2 + str1 is a powerful technique for detecting shared periodicity. If two strings are both made from the same repeating unit, their concatenation is commutative. This same idea can be adapted to test whether one string is a rotation of another: b is a rotation of a if and only if b appears in a + a.

Reducing string problems to integer problems

The leap from "find the longest common divisor string" to "compute gcd of the lengths" is a pattern worth internalizing. Many string problems have elegant solutions that reduce the structural question to a numeric one. Once you compute the right number, the string answer falls out with a simple slice or index operation. You will see similar reductions in problems about repeating patterns, cyclic shifts, and modular string indexing.

The Euclidean GCD algorithm

Python's math.gcd uses the Euclidean algorithm, which repeatedly replaces the larger number with the remainder of dividing the two. It runs in O(log(min(a, b))) time. Understanding how GCD works helps you recognize when a problem has GCD-like structure, even when the problem statement does not mention divisibility explicitly.

Drill string building blocks with spaced repetition

Edge cases

Identical strings. If str1 == str2, then gcd(n, n) = n, and the answer is the entire string. The concatenation check always passes when the strings are equal.
One string is empty. The problem constraints guarantee non-empty strings, but if either were empty, the concatenation check would pass trivially and gcd(0, n) = n, returning the other string.
No common divisor. str1 = "LEET", str2 = "CODE". The concatenation check fails ("LEETCODE" != "CODELEET"), so the answer is "".
One divides the other. str1 = "ABABAB", str2 = "AB". gcd(6, 2) = 2, and "AB" repeated three times gives str1. The answer is "AB".
GCD is 1. str1 = "AA", str2 = "A". gcd(2, 1) = 1, and "A" is the repeating unit. Single-character divisors work the same way.
Different lengths with no divisor. str1 = "ABCDEF", str2 = "ABC". Even though gcd(6, 3) = 3, the concatenation check fails if str1 is not built from repeating str2.

From understanding to recall

The solution is short, just three lines. But reproducing it from memory means recalling three distinct ideas: the concatenation commutativity check, the GCD-of-lengths insight, and the prefix slice. Each idea is simple on its own, but combining them correctly under time pressure requires practice.

Spaced repetition helps you internalize the connection between string periodicity and integer GCD. The first time you solve this problem, the concatenation trick might feel like magic. After a few spaced reviews, it becomes an obvious first move. You stop thinking "how do I check for a common divisor string?" and start thinking "concatenation order test, then GCD." That automatic recognition is what makes the difference in an interview.

Longest Common Prefix - Another string prefix problem that uses character-by-character comparison across multiple strings
Repeated Substring Pattern - Tests whether a single string is built from a repeating unit, using the double-and-search trick
Add Strings - Digit-by-digit string processing that bridges string manipulation and math, similar to how GCD of Strings bridges strings and number theory

Recognizing when a string problem reduces to a math problem is a skill that pays off across many LeetCode categories. Greatest Common Divisor of Strings is one of the cleanest examples of that reduction. Build fluency with the pattern through CodeBricks, and the next time you see repeating structure in strings, the GCD connection will click immediately.

Try CodeBricks free