Hello, Welcome to my August Challenge of Problem Solving and finding solutions to Leetcode's Data Structures and Algorithm questions. Here, I choose a question daily and try to solve it, and finally pen down my process of flow in solving the question.

I hope you find it helpful. Today I will be solving Leetcode question 1071 - Greatest Common Divisor of Strings

Problem Statement

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 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: ""

The Approach

The above problem requires that we find the greatest divisor of the strings. I had two approaches to solving the problem: that is; the brute force approach and secondly using the greedy algorithm

The Brute Force Approach

This is the simplest approach to solving the problem. It involves trying every possible solution until the correct one is found. In this case, the brute force approach would involve trying every possible length of the string x until a length is found that is a divisor of both str1 and str2. This approach is guaranteed to find the correct solution, but it may be very inefficient, especially if the strings are long. The time complexity of this approach is approximately O(min(len(str1), len(str2))^3), considering the nested loops to find substrings and checking the divisor condition.

class Solution:
   def gcdOfStrings(self, str1: str, str2: str) -> str:
        # Helper function to check if a substring is a divisor of a string
        def is_divisor(sub_str, original_str):
          return original_str == sub_str * (len(original_str) // len(sub_str))

        # Find the minimum length between str1 and str2
        min_len = min(len(str1), len(str2))
        largest_divisor = ""

        # Iterate through all possible lengths of substrings
        for l in range(1, min_len + 1):
            # Check if the substring of length l is a divisor of both str1 and str2
            if is_divisor(str1[:l], str1) and is_divisor(str1[:l], str2):
                # Update the largest_divisor if the current substring is larger
                largest_divisor = str1[:l]

        return largest_divisor

How the above code works

The class Solution contains the method to find the largest string x that divides both str1 and str2. The gcdOfStrings method takes two string parameters str1 and str2 and returns the largest string x that divides both strings. The helper function is_divisor, takes two string parameters sub_str (substring) and original_str (original string), and returns True if sub_str is a divisor of original_str, meaning that original_str can be formed by concatenating sub_str multiple times. We then calculate the minimum length between str1 and str2 using the min function and initializes a variable largest_divisor to store the largest common divisor found so far (starting with an empty string). A loop then iterates through all possible lengths of substrings, starting from 1 up to the minimum length between str1 and str2. We then check if the substring of length l (from the beginning of str1) is a divisor of both str1 and str2 by calling the is_divisor function twice. Finally, we update the largest_divisor with the current substring (substring of length l) if it is a divisor of both str1 and str2.

Greedy Algorithm - Most Optimal Approach

This approach involves making the locally optimal choice at each step with the hope of finding a global optimum. In this case, the greedy algorithm would repeatedly add the longest substring of str1 that is also a substring of str2 to the string x. This approach may not always find the correct solution, but it is often much more efficient than the brute force approach. It is a good choice. This is because the greedy algorithm is likely to find a long string that is a divisor of both strings, even if it is not the longest possible string.

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        len1, len2 = len(str1, len(str2))

        # helper function
        def isDivisor(l):
            if len1 % l or len2 % l:
                return False
            f1, f2 = len1 // l, len2 // l
            return str1[:l] * f1 == str1 and str1[:l] * f2 == str2

        for l in range(min(len1, len2), 0, -1):
            if isDivisor(l):
                return str1[:l]
        return ""

How the code works

The given code defines a Solution class with a method gcdOfStrings that finds the largest common divisor string x that divides both str1 and str2. The method first initializes len1 and len2 to the lengths of str1 and str2. Then, it defines a helper function isDivisor(l) that takes an integer l (substring length) and checks if l is a divisor of both str1 and str2. It returns True if l divides both lengths without any remainder and the repeated substrings of str1 and str2 match the original strings. The method then loops through the possible substring lengths, starting from the minimum length between str1 and str2 down to 1. For each length, it calls the isDivisor function to check if it is a common divisor. When it finds the largest common divisor, it returns the substring of str1 of that length. If no common divisor is found, it returns an empty string.

Time Complexity:

The time complexity of the greedy algorithm is O(min(len(str1), len(str2))), and it is more optimal compared to the brute-force approach, which has a time complexity of O(min(len(str1), len(str2))^3).

Space Complexity:

The space complexity of the greedy algorithm is O(1) or constant space complexity. It does not use any extra data structures whose space consumption depends on the size of input strings str1 and str2. The only variables used are len1, len2, f1, f2, and l, which take up constant space regardless of the input size. The helper function isDivisor does not create any data structures or use any significant extra memory.

Optimality over Brute Force:

The second approach is more optimal than the brute-force approach because it reduces the time complexity from O(min(len(str1), len(str2))^3) to O(min(len(str1), len(str2))). In the brute-force approach, we iterated through all possible substring lengths up to the minimum length of str1 and str2, and for each length, we checked if the substring is a divisor using the helper function is_divisor. This led to a cubic time complexity, which can be highly inefficient for large strings.

However, in the greedy approach, we leverage the concept of finding the greatest common divisor (GCD) of the lengths of str1 and str2. The GCD operation allows us to find the largest common divisor string efficiently by considering only the possible lengths that are divisors of both str1 and str2. By doing so, we avoid checking unnecessary lengths and significantly reduce the number of iterations, leading to a linear time complexity. This is why the provided approach is more optimal than the brute-force approach, especially for large strings.

I hope this helps !

#Blind75