[LeetCode] Greatest Common Divisor of Strings

Problem: For two strings s and t, we say "t divides s" if and only if s = 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:

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

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

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

Approach: A simple approach would be to check for every prefix of the smaller string and check if the prefix is such that 

prefix + prefix + prefix + ... + prefix = str1

prefix + prefix + prefix + ... + prefix = str2

We can do some optimization like choosing a prefix such that the length of prefix is divisor of lengths of both str1 and str2 and may be more but whatever optimization we will do the complexity is going to be on higher side i.e. O(m^2 + n^2).

Let's try to see problem from different view, sometimes looking at the examples really help. If you see closely, you can find GCD of str1 and str2 can exist only if 

str1 + str2 = str2 + str1

Why? Let's say GCD of both strings is gcd then:

str1 = gcd + gcd + gcd + ... m times

str2 = gcd + gcd + gcd + ... n times

str1 + str2 = gcd + gcd + gcd + ... (m + n) times

str2 + str1 = gcd + gcd + gcd + ... (n + m) times

so you see str1 + str2 is equal to str2 + str1.

Now that we know when GCD exist, what is GCD of both strings? Just look at the example closely and you will quickly find that GCD is the prefix of length of GCD(Length(str1), Length(str2).

That's all!

Implementation in C#:

Brute-force:

    public string GcdOfStrings(string str1, string str2)

    {

        string gcd = string.Empty;

        int str1Len = str1.Length;

        int str2Len = str2.Length;

        int minStrLen = Math.Min(str1Len, str2Len);

        int currLen = 1;

        if (!string.IsNullOrEmpty(str1) && !string.IsNullOrEmpty(str2))

        {

            while (currLen <= minStrLen)

            {

                if (str1Len % currLen == 0 && str2Len % currLen == 0)

                {

                    string prefix = str1.Substring(0, currLen);

                    if (str2.StartsWith(prefix))

                    {

                        if (this.isStrRepetitionOfPrefix(str1, prefix)

                            && this.isStrRepetitionOfPrefix(str2, prefix))

                        {

                            gcd = prefix;

                        }

                    }

                }

                ++currLen;

            }

        }

        return gcd;

    }

    private bool isStrRepetitionOfPrefix(string str, string prefix)

    {

        int i = prefix.Length;

        while(i < str.Length)

        {

            if (str.Substring(i, prefix.Length) != prefix)

            {

                return false;

            }

            i += prefix.Length;

        }

        return true;

    }

Optimized:

    public string GcdOfStrings(string str1, string str2)

    {

        if (str1 + str2 != str2 + str1)

        {

            return string.Empty;

        }

        int maxLength = str1.Length;

        int minLength = str2.Length;

        if (maxLength < minLength)

        {

            minLength = maxLength;

            maxLength = str2.Length;

        }

        int gcdLength = this.getGCD(maxLength, minLength);

        return str1.Substring(0, gcdLength);

    }

    private int getGCD(int a, int b)

    {

        while (b != 0)

        {

            int temp = b;

            b = a % b;

            a = temp;

        }

        return a;

    }

Complexity: Solution 1: O(m^2 + n^2)

                      Solution 2: O(m + n)