Skip to main content
CodePeetCodePeet
CodePeet 250

Greatest Common Divisor of Strings

EASYProblemSolveExternal Links

Description

We say that a string t divides a string s when s can be formed by concatenating t with itself one or more times. In other words, if you glue copies of t end-to-end, you get exactly s.

Given two strings str1 and str2, find and return the largest string x such that x divides both str1 and str2. If no such string exists, return an empty string "".

This is the string equivalent of the mathematical greatest common divisor (GCD): instead of finding the largest number that divides two numbers, we find the largest repeating pattern that builds both strings.

Examples

Example 1

Input: str1 = "ABCABC", str2 = "ABC"

Output: "ABC"

Explanation: The string "ABC" divides "ABCABC" because "ABC" + "ABC" = "ABCABC" (two copies). It also divides "ABC" because "ABC" itself is one copy. No longer string can divide both, so the answer is "ABC".

Example 2

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

Output: "AB"

Explanation: "AB" divides "ABABAB" because "AB" + "AB" + "AB" = "ABABAB" (three copies). "AB" divides "ABAB" because "AB" + "AB" = "ABAB" (two copies). Although "ABAB" also divides "ABABAB"? No — "ABAB" + "ABAB" = "ABABABAB" which has length 8, not 6. So "AB" is the largest common divisor string.

Example 3

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

Output: ""

Explanation: No string can divide both "LEET" and "CODE". Even single characters fail — 'L' repeated 4 times gives "LLLL", not "LEET". Since no common pattern can rebuild both strings, we return an empty string.

Example 4

Input: str1 = "AAAAAB", str2 = "AAA"

Output: ""

Explanation: "AAA" repeated any number of times gives strings of all 'A's, but "AAAAAB" contains a 'B' at the end. No repeating pattern of "AAA" can produce "AAAAAB". Similarly, no substring of "AAAAAB" can be repeated to form both strings, so the answer is empty.

Constraints

  • 1 ≤ str1.length, str2.length ≤ 1000
  • str1 and str2 consist of English uppercase letters only.

Editorial

Brute Force

Intuition

The most straightforward way to solve this is to try every possible candidate string and check whether it divides both inputs.

What are the candidates? Any divisor string x must be a prefix of both strings. Why? Because when you start repeating x to build str1, the first copy of x forms the beginning of str1. The same logic applies to str2. So x is always a prefix of both strings.

Since we want the greatest (longest) common divisor, we should start checking from the longest possible prefix and work downward. The longest candidate has length equal to the smaller of the two string lengths — because the divisor cannot be longer than either string.

For each candidate length, we extract that prefix from str1, then verify it can rebuild both strings by repeated concatenation. The first candidate that works is our answer.

Step-by-Step Explanation

Let's trace through with str1 = "ABABAB", str2 = "ABAB":

Step 1: Determine the maximum candidate length.

  • len(str1) = 6, len(str2) = 4
  • max_len = min(6, 4) = 4
  • We'll try lengths 4, 3, 2, 1 from longest to shortest.

Step 2: Try candidate length = 4. Extract prefix "ABAB".

  • Does "ABAB" divide "ABABAB"? Repeat: "ABAB" + "ABAB" = "ABABABAB" (length 8). But "ABABAB" has length 6. "ABABABAB" ≠ "ABABAB". No.
  • Candidate length 4 fails.

Step 3: Try candidate length = 3. Extract prefix "ABA".

  • Does "ABA" divide "ABABAB"? Repeat: "ABA" + "ABA" = "ABAABA" (length 6). Compare with "ABABAB". "ABAABA" ≠ "ABABAB". No.
  • Candidate length 3 fails.

Step 4: Try candidate length = 2. Extract prefix "AB".

  • Does "AB" divide "ABABAB"? Repeat: "AB" + "AB" + "AB" = "ABABAB" (length 6). Compare with "ABABAB". Match!
  • Does "AB" divide "ABAB"? Repeat: "AB" + "AB" = "ABAB" (length 4). Compare with "ABAB". Match!
  • Both checks pass!

Step 5: Return "AB" as the greatest common divisor string.

Brute Force — Trying All Prefix Lengths — Watch how we try each prefix length from longest to shortest, checking if the prefix can rebuild both strings through repetition.

Algorithm

  1. Calculate max_len = min(len(str1), len(str2))
  2. For each length L from max_len down to 1:
    a. Extract candidate = str1[0..L-1] (first L characters)
    b. Check if candidate divides str1: repeat candidate until its length equals or exceeds str1, then compare
    c. Check if candidate divides str2: repeat candidate similarly
    d. If both checks pass, return candidate
  3. If no candidate works, return ""

Code

class Solution {
public:
    bool canDivide(string pattern, string target) {
        string built = "";
        while (built.size() < target.size()) {
            built += pattern;
        }
        return built == target;
    }
    
    string gcdOfStrings(string str1, string str2) {
        int maxLen = min(str1.size(), str2.size());
        
        for (int len = maxLen; len >= 1; len--) {
            string candidate = str1.substr(0, len);
            if (canDivide(candidate, str1) && canDivide(candidate, str2)) {
                return candidate;
            }
        }
        
        return "";
    }
};
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        def can_divide(pattern: str, target: str) -> bool:
            built = ""
            while len(built) < len(target):
                built += pattern
            return built == target
        
        max_len = min(len(str1), len(str2))
        
        for length in range(max_len, 0, -1):
            candidate = str1[:length]
            if can_divide(candidate, str1) and can_divide(candidate, str2):
                return candidate
        
        return ""
class Solution {
    private boolean canDivide(String pattern, String target) {
        StringBuilder built = new StringBuilder();
        while (built.length() < target.length()) {
            built.append(pattern);
        }
        return built.toString().equals(target);
    }
    
    public String gcdOfStrings(String str1, String str2) {
        int maxLen = Math.min(str1.length(), str2.length());
        
        for (int len = maxLen; len >= 1; len--) {
            String candidate = str1.substring(0, len);
            if (canDivide(candidate, str1) && canDivide(candidate, str2)) {
                return candidate;
            }
        }
        
        return "";
    }
}

Complexity Analysis

Time Complexity: O(min(m, n) × (m + n))

Where m = len(str1) and n = len(str2). We try up to min(m, n) candidate lengths. For each candidate, the canDivide function builds a string by repeated concatenation, which takes O(m) for str1 and O(n) for str2. In the worst case (no valid divisor), we check all lengths, giving O(min(m, n) × (m + n)).

Space Complexity: O(max(m, n))

The canDivide function constructs a temporary string that can grow up to the length of the target string. This dominates the space usage.

Why This Approach Is Not Efficient

The brute force tries all possible prefix lengths, but most of them are impossible candidates. Consider: if the candidate has length L, it can only divide a string of length N if L evenly divides N (i.e., N % L == 0). A candidate of length 3 can never divide a string of length 7, because 7 is not a multiple of 3.

The brute force blindly tries lengths like 5, 4, 3, etc., even when they mathematically cannot work. With strings up to length 1000, this means wasting time building and comparing strings for candidate lengths that are doomed from the start.

Key insight: We can skip impossible lengths by adding a simple divisibility check. And even better — there is a mathematical property that tells us the exact length of the GCD string without trying multiple candidates.

Better Approach - Length Divisibility Filter

Intuition

We can improve the brute force with one simple observation: if a candidate string of length L divides a string of length N, then N must be a multiple of L. This is because the string is built by repeating the candidate an exact number of times, so the total length must be L × (number of repetitions).

This means we only need to check lengths L where both len(str1) % L == 0 and len(str2) % L == 0. Instead of blindly checking every length from the maximum downward, we skip lengths that cannot possibly work.

Additionally, we can use the more efficient string multiplication check: instead of building the string character by character, directly compute repetitions = N / L and check if candidate × repetitions == target.

Step-by-Step Explanation

Let's trace with str1 = "ABABAB", str2 = "ABAB":

Step 1: Determine the maximum candidate length.

  • len(str1) = 6, len(str2) = 4, max_len = min(6, 4) = 4

Step 2: Try length = 4.

  • Does 6 % 4 == 0? No (6 mod 4 = 2). Skip! We save time by not even constructing or comparing.

Step 3: Try length = 3.

  • Does 6 % 3 == 0? Yes. Does 4 % 3 == 0? No (4 mod 3 = 1). Skip!

Step 4: Try length = 2.

  • Does 6 % 2 == 0? Yes. Does 4 % 2 == 0? Yes. Both divisible — this candidate is worth checking.
  • candidate = "AB"
  • Does "AB" × 3 == "ABABAB"? "ABABAB" == "ABABAB". Yes!
  • Does "AB" × 2 == "ABAB"? "ABAB" == "ABAB". Yes!
  • Both pass!

Step 5: Return "AB".

Length Divisibility Filter — Skipping Impossible Candidates — Watch how the divisibility check lets us skip lengths that cannot possibly work, going straight to valid candidates.

Algorithm

  1. Calculate max_len = min(len(str1), len(str2))
  2. For each length L from max_len down to 1:
    a. If len(str1) % L != 0 or len(str2) % L != 0, skip this length
    b. Extract candidate = str1[0..L-1]
    c. Check if candidate × (len(str1) / L) == str1
    d. Check if candidate × (len(str2) / L) == str2
    e. If both pass, return candidate
  3. Return ""

Code

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        int maxLen = min(str1.size(), str2.size());
        
        for (int len = maxLen; len >= 1; len--) {
            // Skip lengths that can't divide both strings
            if (str1.size() % len != 0 || str2.size() % len != 0) {
                continue;
            }
            
            string candidate = str1.substr(0, len);
            
            // Check if candidate repeated fills str1
            string built1 = "";
            for (int i = 0; i < (int)str1.size() / len; i++) {
                built1 += candidate;
            }
            
            // Check if candidate repeated fills str2
            string built2 = "";
            for (int i = 0; i < (int)str2.size() / len; i++) {
                built2 += candidate;
            }
            
            if (built1 == str1 && built2 == str2) {
                return candidate;
            }
        }
        
        return "";
    }
};
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        max_len = min(len(str1), len(str2))
        
        for length in range(max_len, 0, -1):
            # Skip lengths that can't divide both strings
            if len(str1) % length != 0 or len(str2) % length != 0:
                continue
            
            candidate = str1[:length]
            
            # Check if candidate repeated fills both strings
            reps1 = len(str1) // length
            reps2 = len(str2) // length
            
            if candidate * reps1 == str1 and candidate * reps2 == str2:
                return candidate
        
        return ""
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        int maxLen = Math.min(str1.length(), str2.length());
        
        for (int len = maxLen; len >= 1; len--) {
            // Skip lengths that can't divide both strings
            if (str1.length() % len != 0 || str2.length() % len != 0) {
                continue;
            }
            
            String candidate = str1.substring(0, len);
            
            // Build str1 from candidate
            StringBuilder built1 = new StringBuilder();
            for (int i = 0; i < str1.length() / len; i++) {
                built1.append(candidate);
            }
            
            // Build str2 from candidate
            StringBuilder built2 = new StringBuilder();
            for (int i = 0; i < str2.length() / len; i++) {
                built2.append(candidate);
            }
            
            if (built1.toString().equals(str1) && built2.toString().equals(str2)) {
                return candidate;
            }
        }
        
        return "";
    }
}

Complexity Analysis

Time Complexity: O(min(m, n) × (m + n))

In the worst case, we still try up to min(m, n) lengths (many could pass the divisibility filter). For each passing length, building and comparing takes O(m + n). However, in practice the divisibility filter eliminates many lengths, making this significantly faster than pure brute force on most inputs.

Space Complexity: O(m + n)

We construct two temporary strings (one for each check) during verification. Each can be up to the length of the corresponding input string.

Why This Approach Is Not Efficient

Although the divisibility filter eliminates many candidates, we are still potentially trying multiple lengths. In the worst case — for example, when both strings have length 1000 and their GCD length is 1 — we could check up to 1000 divisors of 1000.

More fundamentally, we are still guessing and checking. There is a mathematical shortcut that tells us the exact length of the GCD string in O(1) time: it must be gcd(len(str1), len(str2)). Combined with a quick validity check, we can solve the entire problem in a single comparison — no loop needed.

Optimal Approach - GCD Length with Concatenation Check

Intuition

Here is the elegant mathematical insight: if a common divisor string exists at all, its length must be gcd(len(str1), len(str2)) — the greatest common divisor of the two string lengths.

Why? Suppose string x of length L divides both strings. Then len(str1) is a multiple of L, and len(str2) is a multiple of L. The largest L that divides both lengths is exactly gcd(len(str1), len(str2)). This is the same GCD we use in number theory.

But knowing the length alone is not enough — we need to confirm a divisor actually exists. Here is the brilliant second insight: a common divisor string exists if and only if str1 + str2 == str2 + str1.

Why does this work? If some pattern x builds both strings, then str1 + str2 is just x repeated (len(str1)/L + len(str2)/L) times, and str2 + str1 is also x repeated the same number of times. So they must be equal. Conversely, if str1 + str2 == str2 + str1, it can be proven that the strings must share a common repeating unit.

So the algorithm is just two steps: check if the concatenation property holds, then extract the prefix of length gcd(m, n).

Step-by-Step Explanation

Let's trace with str1 = "ABABAB", str2 = "ABAB":

Step 1: Check the concatenation property.

  • str1 + str2 = "ABABAB" + "ABAB" = "ABABABABAB"
  • str2 + str1 = "ABAB" + "ABABAB" = "ABABABABAB"
  • Are they equal? "ABABABABAB" == "ABABABABAB". Yes! A common divisor exists.

Step 2: Compute the GCD of the lengths.

  • len(str1) = 6, len(str2) = 4
  • gcd(6, 4) = 2

Step 3: Extract the prefix of length 2.

  • str1[:2] = "AB"

Step 4: Return "AB".

Let's also verify the negative case with str1 = "LEET", str2 = "CODE":

Step 1: Check concatenation property.

  • str1 + str2 = "LEETCODE"
  • str2 + str1 = "CODELEET"
  • "LEETCODE" ≠ "CODELEET". No common divisor exists.

Step 2: Return "" immediately.

GCD + Concatenation Check — Mathematical Shortcut — Watch how a single concatenation comparison determines if a common divisor exists, then the GCD of lengths gives us the exact answer — no loop needed.

Algorithm

  1. Concatenation check: if str1 + str2 != str2 + str1, return "" (no common divisor exists)
  2. Compute gcd_len = gcd(len(str1), len(str2))
  3. Return str1[0..gcd_len-1] (first gcd_len characters of str1)

Code

#include <algorithm>
using namespace std;

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        // If no common divisor exists, concatenations won't match
        if (str1 + str2 != str2 + str1) {
            return "";
        }
        
        // The GCD string length is gcd of both lengths
        int gcdLen = __gcd((int)str1.size(), (int)str2.size());
        return str1.substr(0, gcdLen);
    }
};
from math import gcd

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # If no common divisor exists, concatenations won't match
        if str1 + str2 != str2 + str1:
            return ""
        
        # The GCD string length is gcd of both lengths
        gcd_len = gcd(len(str1), len(str2))
        return str1[:gcd_len]
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // If no common divisor exists, concatenations won't match
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        
        // The GCD string length is gcd of both lengths
        int gcdLen = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdLen);
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Complexity Analysis

Time Complexity: O(m + n)

Where m = len(str1) and n = len(str2). The concatenation check creates two strings of length (m + n) and compares them, which takes O(m + n). The GCD computation takes O(log(min(m, n))) using the Euclidean algorithm. The substring extraction takes O(gcd(m, n)). The dominant term is the concatenation comparison at O(m + n).

Space Complexity: O(m + n)

We create two concatenated strings, each of length m + n, for the comparison. The result string uses at most O(min(m, n)) space. Total space is O(m + n).