Greatest Common Divisor of Strings

Greatest Common Divisor of Strings

What is this problem about?

The Greatest Common Divisor of Strings interview question asks you to find the longest string x that divides both string str1 and string str2. A string x divides a string y if y can be formed by concatenating multiple copies of x. It's exactly like finding the greatest common divisor (GCD) of two numbers, but applied to the repeating patterns of strings.

Why is this asked in interviews?

Companies like Apple, Microsoft, and Amazon use this Math and String coding problem to test a candidate's ability to recognize mathematical properties in string manipulation. It evaluates if you can see beyond complex string matching algorithms and realize that a simple GCD calculation on string lengths (along with a basic concatenation check) provides an elegant $O(N)$ solution.

Algorithmic pattern used

This problem relies on the Greatest Common Divisor (Euclidean Algorithm).

1. Check for validity: If str1 + str2 != str2 + str1, then the two strings don't share a common repeating pattern, and no such divisor exists. Return an empty string.
2. Calculate GCD: If the concatenation check passes, the length of the greatest common divisor string is exactly the GCD of the lengths of str1 and str2.
3. Extract: Return the substring of str1 from index 0 to gcd(len(str1), len(str2)).

Example explanation

str1 = "ABABAB", str2 = "ABAB"

1. Check: "ABABAB" + "ABAB" = "ABABABABAB". "ABAB" + "ABABAB" = "ABABABABAB". They match!
2. Length 1 = 6, Length 2 = 4.
3. GCD(6, 4) = 2.
4. The prefix of length 2 in str1 is "AB". Result: "AB". (Notice "AB" repeated 3 times makes str1, and 2 times makes str2).

Common mistakes candidates make

• Brute Force Slicing: Trying every possible substring length from min(len1, len2) down to 1 and manually verifying if it divides both strings. This works but is slower than the mathematical approach.
• Incorrect GCD implementation: Writing a buggy custom GCD function instead of using the standard Euclidean algorithm gcd(a, b) -> b == 0 ? a : gcd(b, a % b).

Interview preparation tip

Whenever a string problem involves repeating prefixes or patterns across two strings, check if s1 + s2 == s2 + s1. This is a universal trick to confirm that both strings are composed of the exact same repeating base block.