Greatest Common Divisor of Strings
Problem
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2 (i.e., str1 and str2 are concatenations of x one or more times). If no such string exists, return an empty string.
- 1 ≤ str1.length, str2.length ≤ 1000
- str1 and str2 consist of uppercase English letters
Example
str1 = "ABCABC", str2 = "ABC""ABC"The brute-force approach would check all possible substrings of str1 and verify if they divide both strings, which is inefficient. The key insight is that if str1 + str2 != str2 + str1, no common divisor string exists. If they are equal, the greatest common divisor string length must divide both string lengths. Using the gcd of the lengths, we extract the prefix of that length from str1 as the answer.
Approach
Straightforward Solution
A brute-force approach tries all prefixes of str1, checking if they divide both strings. This leads to O(n^3) time complexity due to repeated substring checks and concatenations, which is inefficient for large inputs.
Core Observation
If two strings share a common divisor string, concatenating them in either order must produce the same string (str1 + str2 == str2 + str1). This is a fundamental property of strings formed by repeated concatenations of a common substring.
Path to Optimal
PreviewThe key recognition signals are 'largest string that divides both' and the concatenation equality condition. These indicate a mathematical approach using the greatest common divisor (gcd) of the string lengths…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewFirst, check if str1 + str2 equals str2 + str1. If not, return empty string…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
String concatenation and comparison take O(n) time, where n is the combined length of str1 and str2. Computing gcd is O(log(min(len(str1), len(str2)))). Extracting the prefix is O(k), where k is the gcd length, which is at most n.
Space
O(n)
The concatenated strings str1 + str2 and str2 + str1 require O(n) space. The output string is at most length n. No additional significant auxiliary space is used.
Pattern Spotlight
Math & Geometry (String Divisibility via GCD)
When a problem asks for the largest string that divides two strings, check if concatenations in both orders are equal to confirm divisibility, then use the gcd of lengths to find the maximal repeating unit.
Solution
| 1 | from math import gcd |
| 2 | |
| 3 | class Solution: |
| 4 | def gcdOfStrings(self, str1: str, str2: str) -> str: |
| 5 | if str1 + str2 != str2 + str1: |
| 6 | return "" |
| 7 | |
| 8 | gcd_len = gcd(len(str1), len(str2)) |
| 9 | return str1[:gcd_len] |
Step-by-Step Solution
Verify Concatenation Equality to Confirm Divisibility
| 5 | if str1 + str2 != str2 + str1: |
| 6 | return "" |
Objective
To quickly determine if a common divisor string is possible by checking if str1 + str2 equals str2 + str1.
Key Insight
If two strings are composed of repeated concatenations of a common substring, concatenating them in either order must yield the same string. This check efficiently filters out cases where no common divisor exists, avoiding unnecessary computation.
Interview Quick-Check
Core Logic
The equality check str1 + str2 == str2 + str1 confirms whether the strings share a common repeating pattern.
Common Pitfalls & Bugs
Skipping this check can lead to incorrect results or wasted computation on strings that have no common divisor.
Compute GCD of String Lengths and Extract Divisor
To find the length of the largest common divisor string using gcd and return the corresponding prefix of str1.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if str1 + str2 != str2 + str1:Check if concatenating str1 and str2 in both orders yields the same string.
This equality is a necessary condition for the existence of a common divisor string; if it fails, no such string can divide both inputs.
return ""Return an empty string if the concatenation equality check fails.
Early termination here prevents unnecessary computation when no common divisor string exists, ensuring correctness and efficiency.
gcd_len = gcd(len(str1), len(str2))Compute the greatest common divisor of the lengths of str1 and str2.
The gcd of the lengths determines the length of the largest substring that can be concatenated to form both strings, leveraging a fundamental property of string divisibility.
Full line-by-line criticality + rationale for all 4 lines available on Pro.
Test Your Understanding
Why must str1 + str2 equal str2 + str1 for a common divisor string to exist?
See the answer with Pro.
Related Problems
Math & Geometry pattern
Don't just read it. Drill it.
Reconstruct Greatest Common Divisor of Strings from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Greatest Common Divisor of Strings drill