Solution For Greatest Common Divisor Of Strings

Problem Description:

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

A string x divides a string y if there exists a string z such that y = x + z.

Example 1:

Input: str1 = “ABCABC”, str2 = “ABC”
Output: “ABC”
Example 2:

Input: str1 = “ABABAB”, str2 = “ABAB”
Output: “AB”

Solution:

To find the GCD of two strings s1 and s2, we need to keep checking for the common divisors of both the strings from their start.

Steps to solve the problem:

1. If both strings are empty, return an empty string.

2. If either of the strings is empty, return the other string.

3. Check if the length of s1 is less than s2.

If it is, swap s1 and s2.

1. Check if s1 is divisible by s2.

If it is, return s2.

1. Otherwise, divide s1 by s2 and subtract the remainder from s1.

2. Repeat the steps 3 to 5 until s1 is empty or s2 is empty.

3. If either of the strings is empty, return the other string.

Let’s implement this algorithm in python:

def gcdOfStrings(str1: str, str2: str) -> str:
if len(str1) == 0 or len(str2) == 0:
return ”
if len(str1) < len(str2):
str1, str2 = str2, str1
if str1 == str2:
return str1

if str1.startswith(str2):
    return gcdOfStrings(str1[len(str2):], str2)

return ''

Time Complexity:

The time complexity of the above solution is O(n^2), where n is the length of the longest string.

Space Complexity:

The space complexity of the above solution is O(n), where n is the length of the longest string.

Step by Step Implementation For Greatest Common Divisor Of Strings

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // if str1 is not a multiple of str2, then str2 cannot be a multiple of str1
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        // gcd(a, b) = gcd(a-b, b) or gcd(a, b-a)
        return str1.substring(0, gcd(str1.length(), str2.length()));
    }
    // greatest common divisor
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

def gcdOfStrings(str1, str2): 
    
    if (str1 == str2): 
        return str1 
    
    if (str1 > str2): 
        return gcdOfStrings(str2, str1) 
        
    for i in range(len(str1), 0, -1): 
        if (len(str2) % i == 0 and len(str1) % i == 0): 
            if (str2[:i] == str1[:i]): 
                return str2[:i] 
                
    return ""

function gcdOfStrings(str1, str2) {
    if (str1.length == 0 || str2.length == 0) {
        return "";
    }
    if (str1 == str2) {
        return str1;
    }
    if (str1.length > str2.length) {
        return gcdOfStrings(str1.substr(0, str2.length), str2);
    }
    return gcdOfStrings(str1, str2.substr(0, str1.length));
};

One possible solution to this problem is as follows:

// Find the greatest common divisor of two strings

string gcdOfStrings(string str1, string str2) {
    
    // If either string is empty, then the other string is the GCD
    if (str1.empty() || str2.empty()) {
        return str1.empty() ? str2 : str1;
    }
    
    // If the strings are not of equal length, then they cannot have a GCD
    if (str1.length() != str2.length()) {
        return "";
    }
    
    // We can find the GCD by iteratively removing the common prefix from
    // both strings until they are equal
    while (str1 != str2) {
        if (str1.length() > str2.length()) {
            str1 = str1.substr(str2.length());
        } else {
            str2 = str2.substr(str1.length());
        }
    }
    
    return str1;
}

public class Solution {
    public string GcdOfStrings(string str1, string str2) {
        if (str1.Length == 0 || str2.Length == 0) return "";
        if (str1.Length < str2.Length) return GcdOfStrings(str2, str1);
        if (str2 == "") return str1;
        if (str1.Substring(0, str2.Length) != str2) return "";
        return GcdOfStrings(str1.Substring(str2.Length), str2);
    }
}