#1071

Easy

LeetCode Problem Workspace

Greatest Common Divisor of Strings

Find the greatest common divisor string between two strings based on the math and string patterns.

Problem Statement

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2. A string t divides another string s if s can be formed by concatenating t multiple times. The goal is to find the largest such string that divides both input strings.

For example, with str1 = "ABCABC" and str2 = "ABC", the greatest common divisor of these strings is "ABC", as it divides both strings. In other cases, like str1 = "LEET" and str2 = "CODE", no common divisor string exists, and the output is an empty string.

Examples

Example 1

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

Output: "ABC"

Example details omitted.

Example 2

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

Output: "AB"

Example details omitted.

Example 3

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

Output: ""

Example details omitted.

Constraints

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

Solution Approach

Check Possible Prefixes

Start by checking if the greatest common divisor could be any prefix of str1 or str2. The greatest common divisor must be a prefix of both strings.

String Divisor Validation

For each potential prefix, verify if repeating it forms both str1 and str2. This step involves checking if the prefix divides both strings without remainder.

Return the Largest Valid Prefix

Once the valid prefix is found, return it as the solution. If no valid prefix divides both strings, return an empty string.

Complexity Analysis

Metric	Value
Time	O(m + n)
Space	O(m + n)

The time complexity is O(m + n), where m and n are the lengths of str1 and str2. This comes from the need to check each prefix and validate its divisibility. The space complexity is O(m + n) due to the space used for string operations and comparisons.

What Interviewers Usually Probe

Candidate understands string manipulation and divisibility patterns.
Candidate shows awareness of efficiency in checking string prefixes.
Candidate demonstrates clear reasoning in validating the divisor.

Common Pitfalls or Variants

Common pitfalls

Forgetting that the greatest common divisor must be a prefix of both strings.
Not checking for an empty string result when no common divisor is found.
Assuming the solution always involves finding a non-empty divisor string.

Follow-up variants

What if both strings have no common divisor?
What if one string is a multiple of the other, but not a perfect divisor?
How does the problem change if strings contain lower case letters?

FAQ

How do I find the greatest common divisor of two strings?

You can find the greatest common divisor by checking possible prefixes and validating if repeating them forms both strings.

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

The time complexity is O(m + n), where m and n are the lengths of the two strings.

What happens if there is no common divisor string?

If there is no common divisor, the solution is an empty string.

What are some common mistakes when solving the Greatest Common Divisor of Strings problem?

Common mistakes include not verifying that the divisor must be a prefix of both strings or overlooking the empty string case.

How does GhostInterview help with solving the Greatest Common Divisor of Strings problem?

GhostInterview provides guidance on efficient solutions, helps avoid pitfalls, and ensures edge cases like empty results are handled properly.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        def check(a, b):
            c = ""
            while len(c) < len(b):
                c += a
            return c == b

        for i in range(min(len(str1), len(str2)), 0, -1):
            t = str1[:i]
            if check(t, str1) and check(t, str2):
                return t
        return ''

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        def check(a, b):
            c = ""
            while len(c) < len(b):
                c += a
            return c == b

        for i in range(min(len(str1), len(str2)), 0, -1):
            t = str1[:i]
            if check(t, str1) and check(t, str2):
                return t
        return ''

Continue Practicing

#1041 robot bounded in circle #1154 day of the year #972 equal rational numbers