LeetCode75 - Greatest Common Divisor of Strings #2

Hi there!

So this is the 2nd challenge in leetcode 75, we're still tackling with array&hashing problem, so let's jump right into it.

Problem Statement

Given two strings str1 and str2, find the largest string x that divides both strings. If no such string exists, return an empty string.
Example Scenarios

str1 = "ABCABC", str2 = "ABC"

Output: "ABC"
Explanation: "ABC" divides both input strings perfectly

str1 = "ABABAB", str2 = "ABAB"

Output: "AB"
Explanation: "AB" divides both input strings perfectly

Solution Strategy

1. Start from the length of the shorter string
2. Decrease length in each iteration
3. Validate if current length produces a valid divisor

Key Validation Conditions

• Divisor length must evenly divide both string lengths
• Repeating the divisor should reconstruct original strings

func gcdOfStrings(_ str1: String, _ str2: String) -> String {
   func isDivisor(_ factor: Int) -> Bool {
       if str1.count % factor != 0 || str2.count % factor != 0 {
           return false
       }

       let stringDivisor = String(str1.prefix(factor))

       return String(repeating: stringDivisor, count: str1.count / factor) == str1 && 
              String(repeating: stringDivisor, count: str2.count / factor) == str2
   }

   for i in stride(from: min(str1.count, str2.count), to: 0, by: -1) {
       if isDivisor(i) {
           return String(str1.prefix(i))
       }
   }

   return ""
}