1071. Greatest Common Divisor of Strings

Problem Statement

link: LeetCode.cn LeetCode

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

Solution Approach

The algorithm checks for the greatest common divisor of the lengths of the two strings and verifies if substrings of that length can divide both strings, returning the maximum common divisor substring found.

Algorithm

1. Find Divisors: Determine common divisors of string lengths.
2. Check Substrings: Verify if substrings of these lengths divide both strings.
3. Return Maximum: Output the longest substring that meets the criteria, or an empty string if none exist.

Implement

    class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        l1, l2 = len(str1), len(str2)
        res = ""
        for i in range(1, l2 + 1):
            if l1 % i == 0 and l2 % i == 0:
                if str1[:i] * (l1 // i) == str1 and str1[:i] * (l2 // i) == str2:
                    res = str1[:i]
        return res
        

    
    

Twitter  facebook  Email