Finding the Greatest Common Divisor of Two Strings Without GCD

Problem Statement

Given two strings str1 and str2, we need to find the largest string X such that both str1 and str2 are formed by repeating X multiple times.

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:"" (No common divisor string)

Approach (Without Using GCD from math library)

Since we cannot use math.gcd, we manually find the largest common divisor string by checking substrings of str2 from longest to shortest.

Steps to Solve the Problem

1. Ensure str2 is the smaller string – swap if necessary.

2. Iterate through possible substring lengths from longest to shortest.

3. Check divisibility conditions:

   • The substring must be able to construct both str1 and str2 by repeating itself.

     
     

Implementation

def gcdOfStrings(str1, str2):
    len1, len2 = len(str1), len(str2)

    # Ensure str2 is the shorter string
    if len2 > len1:
        str1, str2 = str2, str1
        len1, len2 = len2, len1

    # Try all possible substrings of str2 from longest to shortest
    for i in range(len2, 0, -1):
        sub_string = str2[:i]  # Candidate substring
        len_sub = len(sub_string)

        # Check if sub_string can form both str1 and str2
        if (len2 % len_sub == 0 and len1 % len_sub == 0 and
            sub_string * (len2 // len_sub) == str2 and
            sub_string * (len1 // len_sub) == str1):
            return sub_string

    return ""

# Example Usage
print(gcdOfStrings("ABCABC", "ABC"))  # Output: "ABC"
print(gcdOfStrings("ABABAB", "ABAB")) # Output: "AB"
print(gcdOfStrings("LEET", "CODE"))   # Output: ""

Explanation

1. Loop through all possible substrings of str2 from longest to shortest.

2. For each candidate substring sub_string, check:

   • If it can evenly divide both str1 and str2 (length divisibility conditions).

   • If repeating it forms the original strings.

3. Return the largest valid substring found; otherwise, return "".

Time Complexity Analysis

• Iterating over substrings: Worst case O(N).

• Checking divisibility and forming repeated strings: O(N).

• Total Complexity: O(N²) in the worst case.

  
  

This approach efficiently finds the greatest common divisor string without using the gcd function. 🚀 Let me know if you have any questions or suggestions!