Greatest Common Divisor of Strings

Problem Statement

Greatest Common Divisor of Strings

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.

LOGIC

The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two integers. The GCD is the largest positive integer that divides both numbers without leaving a remainder.

How the Euclidean Algorithm Works

The Euclidean algorithm is based on the principle that the GCD of two numbers also divides their difference. The algorithm uses the following steps:

1. Given Two Numbers: Suppose you have two positive integers, a and b, where a ≥ b.
2. Apply the Modulus Operation: Calculate the remainder when a is divided by b, denoted as r = a % b.
3. Recursive Step: Replace a with b, and replace b with r. Now, find the GCD of b and r.
4. Repeat: Continue this process until r (the remainder) becomes 0. When r = 0, the algorithm stops, and the GCD is the last non-zero remainder.

Example of the Euclidean Algorithm

Let’s find the GCD of 252 and 105:

1. Step 1: a=252 , b=105
   • Compute r = 252%105 = 42
   • Replace a with 105 and b with 42
2. Step 2: a=105, b=42
   • Compute r = 105%42 = 21
   • Replace a with 42 and b with 21
3. Step 3: a=42, b=21
   • Compute r = 42%21 = 0
   • Replace a with 21 and b with 0
4. End: Since b=0, the algorithm stops, and the GCD is the last non-zero remainder, which is 21.

Why the Euclidean Algorithm Works

The key insight behind the Euclidean algorithm is that the GCD of two numbers a and b is the same as the GCD of b and a % b. This is because any divisor of both b and a % b must also divide a. Conversely, any divisor of a and b also divides a % b.

Time Complexity of the Euclidean Algorithm

The time complexity of the Euclidean algorithm is O(log⁡(min⁡(a,b))). This logarithmic complexity is due to the fact that the size of the numbers involved reduces significantly with each step.

Summary

• The Euclidean algorithm finds the GCD by iteratively replacing the larger number with its remainder when divided by the smaller number.
• It stops when the remainder is zero, and the last non-zero remainder is the GCD.
• The algorithm is efficient, with a time complexity of O(log⁡(min⁡(a,b)))

JAVA CODE

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1+str2).equals(str2+str1)) {
            return "";
        }

        int gcdLength = gcd(str1.length(), str2.length());

        // return the substring from the start up to gcdLength
        return str1.substring(0, gcdLength);
    }

    public static int gcd(int a, int b){
        if (b==0){
            return a;
        }

        return gcd(b, a%b);
    }
}

GOLANG CODE

func gcdOfStrings(str1 string, str2 string) string {
    if (str1+str2 != str2+str1) {
        return ""
    }

    gcdLength := gcd(len(str1), len(str2))
    return str1[:gcdLength]
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

Explanation

1. GCD of Lengths: The first step is to compute the GCD of the lengths of the two strings. This will give the length of the potential GCD string.
2. Check for Valid GCD: For a valid GCD string to exist, concatenating the two strings in any order should yield the same result (i.e., str1 + str2 should equal str2 + str1). If this condition is not met, there is no common divisor, so the result should be an empty string.
3. Extract the GCD String: If the above condition is satisfied, the greatest common divisor string will be the first gcdLength characters of str1.

Example Run

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

This implementation efficiently finds the GCD of the two strings based on their lengths and the concatenation condition.

Time Complexity

1. GCD Calculation:
   • The time complexity of the gcd function is O(log⁡(min⁡(m,n))) where m and n are the lengths of the two strings. This is because the Euclidean algorithm, used to compute the GCD of two integers, runs in logarithmic time.
2. String Concatenation Check:
   • The string concatenation check (str1 + str2 == str2 + str1) involves concatenating the strings and comparing them. The concatenation operation itself is O(m+n), and the comparison also takes O(m+n). Thus, this step has a time complexity of O(m+n).

So, the overall time complexity is dominated by the string concatenation check:

Time Complexity: O(m+n)

Space Complexity

1. Auxiliary Space:
   • The space required for the GCD computation is constant, i.e., O(1).
   • The space used by the string concatenation (str1 + str2 and str2 + str1) is O(m+n).
2. Output String:
   • The output string, which is a substring of str1, has a length equal to the GCD of the lengths of str1 and str2, so it requires O(gcd(m,n)) space.

However, the concatenation space is temporary and doesn’t persist beyond the check. Therefore, the overall space complexity is driven by the substring output:

Space Complexity: O(gcd(m,n))

Summary

• Time Complexity: O(m+n)
• Space Complexity: O(gcd(m,n))

Visit https: https://codeandalgo.com for more such contents.