Jobs

Interviews

Discussions

Greatest Common Divisor of Strings

Easy

Apple

2 views

Topics:

StringsGreedy Algorithms

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.

Greatest Common Divisor of Strings

Easy

Apple

2 views

Topics:

StringsGreedy Algorithms

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.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings str1 and str2 be empty or null?
Are the input strings guaranteed to contain only printable ASCII characters, or should I handle other character sets?
If there is no greatest common divisor string, what should I return: an empty string, null, or throw an exception?
By 'divides', do you mean that the string is formed by repeating the GCD string one or more times?
Are the lengths of str1 and str2 guaranteed to be within a specific range?

Brute Force Solution

Approach

The brute force approach for finding the greatest common divisor (GCD) string involves checking every possible substring length to see if it divides both input strings evenly. We start with the shortest possible substring and gradually increase the length, verifying if it can be repeated to form the original strings. Once a divisor is found, the algorithm checks if a longer prefix exists, returning the longest of such prefixes.

Here's how the algorithm would work step-by-step:

Start by considering every possible length, starting from length 1 up to the length of the shorter input string.
For each length, take the substring of that length from the beginning of both strings.
Check if repeating that substring creates the first full string.
Also check if repeating the same substring creates the second full string.
If the substring can be repeated to form both strings, we've found a common divisor.
If a longer substring is a common divisor, replace our current solution with the longer substring.
Continue this process until we've checked substrings of all possible lengths.
The last common divisor we found (if any) is the greatest common divisor string.

Code Implementation

def greatest_common_divisor_of_strings_brute_force(first_string, second_string):
    shorter_string_length = min(len(first_string), len(second_string))
    greatest_common_divisor = ""

    for substring_length in range(1, shorter_string_length + 1):
        substring = first_string[:substring_length]

        # Check if the substring evenly divides the first string
        if len(first_string) % substring_length == 0:
            first_string_divisor_count = len(first_string) // substring_length
            repeated_first_string = substring * first_string_divisor_count

            if repeated_first_string == first_string:

                # Check if the substring evenly divides the second string
                if len(second_string) % substring_length == 0:
                    second_string_divisor_count = len(second_string) // substring_length
                    repeated_second_string = substring * second_string_divisor_count

                    if repeated_second_string == second_string:
                        greatest_common_divisor = substring

    return greatest_common_divisor

Big(O) Analysis

Time Complexity

O(n*m) – The primary loop iterates up to the length of the shorter string, which we can denote as m. Inside this loop, we create substrings of length i. The isDivisor function checks if a substring divides both strings, which involves string comparisons that take O(n/i) and O(m/i) time respectively, where n is the length of the first string. Therefore, the overall time complexity can be approximated as the sum from i = 1 to m of (n/i + m/i), leading to approximately O(n*m) in the worst case because the iterations and comparisons scale directly with input lengths. Thus, we can simplify it to O(n*m).

Space Complexity

O(1) – The algorithm's space complexity is constant, O(1), because it primarily uses a fixed number of variables to store lengths and substrings. The substrings extracted from the input strings are stored in temporary variables, but the size of these variables is bounded by the length of the shorter string. Since the algorithm only stores a few variables regardless of the input string lengths, the space used does not scale with the input size.

Optimal Solution

Approach

This problem asks us to find the largest string that perfectly divides both input strings. We can solve this efficiently by checking if the shorter string is a repeating unit of the longer string, and then finding the greatest common divisor of their lengths.

Here's how the algorithm would work step-by-step:

First, check if joining the two strings in either order results in the same combined string. If not, there's no common divisor string, so return an empty string.
If joining them in either order results in the same string, find the length of each string.
Compute the greatest common divisor (GCD) of the lengths of the two strings. You can use the Euclidean algorithm for this.
The substring of either string, starting from the beginning and with a length equal to the GCD you just calculated, is the greatest common divisor string. Return this substring.

Code Implementation

def greatest_common_divisor_of_strings(string1, string2):
    if string1 + string2 != string2 + string1:
        return ""

    # Euclidean algorithm for GCD
    def gcd(length_of_string1, length_of_string2):
        while(length_of_string2):
            length_of_string1, length_of_string2 = length_of_string2, length_of_string1 % length_of_string2
        return length_of_string1

    len_string1 = len(string1)
    len_string2 = len(string2)

    # GCD is needed to determine length of substring
    greatest_common_divisor = gcd(len_string1, len_string2)

    # Return the substring from the beginning
    return string1[:greatest_common_divisor]

Big(O) Analysis

Time Complexity

O(m + n) – The initial check `str1 + str2 == str2 + str1` involves string concatenation and comparison, which takes O(m + n) time, where m and n are the lengths of str1 and str2, respectively. The Euclidean algorithm to find the GCD of the string lengths takes O(log(min(m, n))) time, which is dominated by O(m + n). Extracting the substring of length GCD takes O(min(m, n)) time, also dominated by O(m + n). Therefore, the overall time complexity is O(m + n).

Space Complexity

O(1) – The algorithm primarily uses a few integer variables to store lengths and the GCD, regardless of the input string lengths. The substring operation extracts a portion of the input string but does not create a new string of significant size relative to the input, and the GCD calculation using the Euclidean algorithm uses constant space. Therefore, the auxiliary space used is constant and independent of the input string lengths, denoted as N (where N is the combined length of the two input strings). Hence, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string inputs (str1 = '' or str2 = '')	Return an empty string, as an empty string is considered a divisor of any string.
One string is a prefix of the other, but not a divisor (e.g., str1 = 'ABCABC', str2 = 'ABC')	The Euclidean algorithm correctly finds the GCD in this case by iteratively reducing the larger string.
Strings have no common divisor other than the empty string (e.g., str1 = 'ABC', str2 = 'DEF')	The Euclidean algorithm will eventually result in empty strings, which will be handled correctly.
Extremely long strings that could cause performance issues.	The Euclidean algorithm approach is efficient, with complexity related to the string lengths not requiring excessive resources.
str1 and str2 are identical strings.	The algorithm should return the identical string as the GCD.
Input strings contain non-alphanumeric characters.	Assume input strings contain only alphanumeric characters as the question specifies 'strings'; handle other character types via input sanitization or validation before the core logic is executed.
str1 or str2 is null.	Throw IllegalArgumentException or return null based on the API contract.
One string is a multiple repetition of the other (e.g., str1 = 'ABABAB', str2 = 'AB')	The Euclidean algorithm efficiently handles this by reducing the larger string to 'AB'.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings str1 and str2 be empty or null?
Are the input strings guaranteed to contain only printable ASCII characters, or should I handle other character sets?
If there is no greatest common divisor string, what should I return: an empty string, null, or throw an exception?
By 'divides', do you mean that the string is formed by repeating the GCD string one or more times?
Are the lengths of str1 and str2 guaranteed to be within a specific range?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering every possible length, starting from length 1 up to the length of the shorter input string.
For each length, take the substring of that length from the beginning of both strings.
Check if repeating that substring creates the first full string.
Also check if repeating the same substring creates the second full string.
If the substring can be repeated to form both strings, we've found a common divisor.
If a longer substring is a common divisor, replace our current solution with the longer substring.
Continue this process until we've checked substrings of all possible lengths.
The last common divisor we found (if any) is the greatest common divisor string.

Code Implementation

def greatest_common_divisor_of_strings_brute_force(first_string, second_string):
    shorter_string_length = min(len(first_string), len(second_string))
    greatest_common_divisor = ""

    for substring_length in range(1, shorter_string_length + 1):
        substring = first_string[:substring_length]

        # Check if the substring evenly divides the first string
        if len(first_string) % substring_length == 0:
            first_string_divisor_count = len(first_string) // substring_length
            repeated_first_string = substring * first_string_divisor_count

            if repeated_first_string == first_string:

                # Check if the substring evenly divides the second string
                if len(second_string) % substring_length == 0:
                    second_string_divisor_count = len(second_string) // substring_length
                    repeated_second_string = substring * second_string_divisor_count

                    if repeated_second_string == second_string:
                        greatest_common_divisor = substring

    return greatest_common_divisor

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if joining the two strings in either order results in the same combined string. If not, there's no common divisor string, so return an empty string.
If joining them in either order results in the same string, find the length of each string.
Compute the greatest common divisor (GCD) of the lengths of the two strings. You can use the Euclidean algorithm for this.
The substring of either string, starting from the beginning and with a length equal to the GCD you just calculated, is the greatest common divisor string. Return this substring.

Code Implementation

def greatest_common_divisor_of_strings(string1, string2):
    if string1 + string2 != string2 + string1:
        return ""

    # Euclidean algorithm for GCD
    def gcd(length_of_string1, length_of_string2):
        while(length_of_string2):
            length_of_string1, length_of_string2 = length_of_string2, length_of_string1 % length_of_string2
        return length_of_string1

    len_string1 = len(string1)
    len_string2 = len(string2)

    # GCD is needed to determine length of substring
    greatest_common_divisor = gcd(len_string1, len_string2)

    # Return the substring from the beginning
    return string1[:greatest_common_divisor]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string inputs (str1 = '' or str2 = '')	Return an empty string, as an empty string is considered a divisor of any string.
One string is a prefix of the other, but not a divisor (e.g., str1 = 'ABCABC', str2 = 'ABC')	The Euclidean algorithm correctly finds the GCD in this case by iteratively reducing the larger string.
Strings have no common divisor other than the empty string (e.g., str1 = 'ABC', str2 = 'DEF')	The Euclidean algorithm will eventually result in empty strings, which will be handled correctly.
Extremely long strings that could cause performance issues.	The Euclidean algorithm approach is efficient, with complexity related to the string lengths not requiring excessive resources.
str1 and str2 are identical strings.	The algorithm should return the identical string as the GCD.
Input strings contain non-alphanumeric characters.	Assume input strings contain only alphanumeric characters as the question specifies 'strings'; handle other character types via input sanitization or validation before the core logic is executed.
str1 or str2 is null.	Throw IllegalArgumentException or return null based on the API contract.
One string is a multiple repetition of the other (e.g., str1 = 'ABABAB', str2 = 'AB')	The Euclidean algorithm efficiently handles this by reducing the larger string to 'AB'.