Euclid’s Algorithm for Greatest Common Divisor ON STRINGS.

Application of Euclid’s Algorithm for Greatest Common Divisor on solving string problems — number theory touching strings!

The LC problem 1071 Greatest Common Divisor of Strings is marked as EASY on the platform.

In my opinion, easy problems are not marked easy just because the solution is easy to think of, they also may be marked so because their acceptance criteria is forgiving.

Such is the case with this problem too. Every problem has a brute force solution, most of the time it’s not accepted by the platform. As the optimisation might be tricky, the difficulty might be bumped up to medium, or in certain cases hard too.

For this particular problem, the platform accepts the brute force solution too.

The Brute Force Approach

Find the smaller string and check conditions for each of its prefix strings.

FUNCTION gcdOfStrings(str1, str2):

    temp ← empty string
    ans  ← empty string

// FIND THE SMALLER STRING
    IF length(str1) > length(str2):
        smaller ← str2
        longer  ← str1
    ELSE:
        smaller ← str1
        longer  ← str2

    FOR i FROM 0 TO length(smaller) - 1:

        temp ← temp + smaller[i]

// FOR  EACH PREFIX, FIND OUT THE NUMBER OF TIMES IT MUST BE REPEATED TO
// REACH THE LENGTH OF EACH OF THE STRINGS
        s ← length(smaller) / length(temp)
        l ← length(longer) / length(temp)

// REPEAT THE SUBSTRING AND CHECK IF IT SATISFIES THE CONDITION
// STORE SATISFYING STRING IN SEPARATE VARIABLE
        IF smaller == repeat(temp, s) AND
           longer  == repeat(temp, l):

            ans ← temp

    RETURN ans

**Time Complexity for this algorithm: **O(n²), closer to O(n³) in many languages

**Space Complexity for this algorithm: **O(max(n, m)), where n is the length of str1 and m is the length of str2.

The LC constraints are forgiving here (also for the well-versed in DSA the invariant is short once known), that’s why it will still pass. But AC on LeetCode is not the end of the problem, it’s just the beginning.

The OPTIMAL Approach

In order to understand the optimal approach of this problem, we must know what the Euclid’s Algorithm for Greatest Common Divisor is.

EUCLID’S ALGORITHM FOR GREATEST COMMON DIVISOR

// The Euclid's Algorithm for Greatest Common Divisor states
gcd(a,b) = gcd(b,a%b)

Yes, this algorithm is recursive, for people familiar with recursion, the base case is in the algorithm below, for ones new to it, you can skip to the iterative algorithm.

Recursive Algorithm

// RECURSIVE VERSION
FUNCTION gcd(a,b):

// Yes, this is the base case
  if b==0:
    RETURN a

  RETURN gcd(b,a%b)

Iterative Algorithm

// ITERATIVE VERSION
FUNCTION gcd(a,b):

// Yes, this is the condition, once b reaches 0, a is our answer
  WHILE(b!=0):
    temp=b
    b=a%b
    a=temp

  return a

Time Complexity: O(log(min(n, m))) Space Complexity: O(1)

How does this work, you ask, this is an identity, that which we will prove some other time. Once done, I will link that writeup here. Until then, We treat this identity as given here; its proof is classical!

The CORE

The core of this problem is finding the largest prefix string, that can be repeated to form both of the strings. i.e. Both of the strings can be formed by the prefix string. So, str1+str2 should be equal to str2+str1.

Think about it:

Let t be the prefix string that satisfies the condition, let str1 = t + t + t …. + t (x times), str2 = t + t + t … + t (y times) so, str1 + str2 = t + t + t + … + t (x+y times) and str2 + str1 = t + t + t + … + t (y+x times)

Now, if this condition is not valid, there won’t exist any prefix string that can form both the strings, so the answer automatically is an empty string, no need to check further. All cases with no answer get solved instantly, no need to even look for an answer. This condition is exhaustive for the existence of a valid answer.

Now, to the actual solution part.

Suppose str1 = “ABCABCABC” and str2 = “ABCABC”

length(str1) = 9, length(str2) = 6 str1+str2 = “ABCABCABCABCABC” str2+str1 = “ABCABCABCABCABC”

so, first condition satisfied. Now, in order to find the GCD, all we have to do is return the substring of length GCD of length of str1 and length of str2.

// for the above example
GCD(length(str1),length(str2))
= GCD(9,6)
= 3

So, answer is substring(str1, 0, 3) = "ABC"

Let’s sum it all up

FUNCTION gcdOfStrings(str1, str2):

    // STEP 1:
    // If both strings are made from the same repeating pattern,
    // then concatenating them in any order should give the same result
    IF (str1 + str2) ≠ (str2 + str1):
        RETURN ""

    // STEP 2:
    // Find the greatest common divisor of the string lengths
    //(use recursive or iterative approach as per your discretion)
    gcdLen ← GCD(length(str1), length(str2))

    // STEP 3:
    // The GCD string must be the prefix of length gcdLen
    RETURN substring(str1, 0, gcdLen)

Time Complexity for this algorithm: O(n + m) due to the string concatenation.

Space Complexity for this algorithm: O(n + m) with explicit concatenation O(1) extra space if concatenation is avoided via index checks

It’s just one of the many beautiful ways number theory intersects with strings.

So, if we had left this question at AC with the brute force, we would have never stumbled onto the application of Euclid’s Algorithm for GCD being applicable on strings.

Thus, my suggestion, go beyond the acceptable, you might learn something new.