Is Greatest Common Divisor of Strings easy or hard?

The problem is classified as Easy on LeetCode. The main challenge is spotting the mathematical insight that links string repetition with the GCD of lengths. Once that observation is made, the implementation is short and efficient.

How to solve Greatest Common Divisor of Strings in O(n)?

Check if str1 + str2 equals str2 + str1. If they differ, no common divisor string exists. If they match, compute gcd(len(str1), len(str2)) using the Euclidean algorithm and return the prefix of that length from either string. The overall complexity is O(n+m).

Greatest Common Divisor of Strings Python or Java solution

In Python or Java, compute gcd(len(str1), len(str2)) using the built-in math utilities or a Euclidean algorithm implementation. After verifying str1 + str2 equals str2 + str1, return str1.substring(0, gcdLength) or str1[:gcdLength].

What is the best approach for Greatest Common Divisor of Strings?

The most efficient approach uses the GCD of the string lengths. First verify that str1 + str2 equals str2 + str1 to ensure both strings share the same repeating base pattern. Then compute gcd(len(str1), len(str2)) and return the prefix of that length. This runs in O(n+m) time with O(1) extra space.

Is Greatest Common Divisor of Strings asked at Google Amazon Meta?

String pattern and GCD-based reasoning problems appear in interviews at companies like Google, Amazon, and Meta. This problem tests pattern recognition, mathematical reasoning with GCD, and efficient string manipulation.

What data structure is used in Greatest Common Divisor of Strings?

The problem primarily uses string operations and a mathematical GCD calculation. No advanced data structures are required. The key concepts involve string concatenation checks and computing the greatest common divisor of two integers.

What is the time complexity of Greatest Common Divisor of Strings?

The optimal solution runs in O(n+m) time because it compares concatenated strings once and computes the numeric GCD of the lengths. Space complexity is O(1). A brute-force substring checking approach can take up to O((n+m) * min(n,m)) time.

Description Hints 1 Solution Video 9:16

1071. Greatest Common Divisor of Strings

Easy54.1% acceptance7 companies

For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + t + t (i.e., t is concatenated 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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= str1.length, str2.length <= 1000
str1 and str2 consist of English uppercase letters.

Asked at 7 companies

Tiktok

Google Amazon Microsoft Meta Bloomberg Oracle

Topics

Math String

Hints open one at a time

Hint 1

The greatest common divisor must be a prefix of each string, so we can try all prefixes.

9:16

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution