Solution

Our strategy will pivot to finding the largest substring which, when repeated, can reconstruct both input strings. This is akin to finding the GCD in numbers but applied to string patterns.

To find the GCD of two strings, we aim to identify the longest string that can be repeatedly concatenated to produce both input strings. This concept mirrors the GCD in numbers, where we seek the largest number that divides both inputs without leaving a remainder. In strings, division is analogous to concatenation.

Test Cases

// MARK: - Test Cases

let solution = Solution()

// Test Case 1
let str1_1 = "ABCABC"
let str2_1 = "ABC"
print("Test Case 1: \\\\(solution.gcdOfStrings(str1_1, str2_1))")
// Expected Output: "ABC"

// Test Case 2
let str1_2 = "ABABAB"
let str2_2 = "ABAB"
print("Test Case 2: \\\\(solution.gcdOfStrings(str1_2, str2_2))")
// Expected Output: "AB"

// Test Case 3
let str1_3 = "LEET"
let str2_3 = "CODE"
print("Test Case 3: \\\\(solution.gcdOfStrings(str1_3, str2_3))")
// Expected Output: ""

// Test Case 4
let str1_4 = "TAUTAUTAU"
let str2_4 = "TAU"
print("Test Case 4: \\\\(solution.gcdOfStrings(str1_4, str2_4))")
// Expected Output: "TAU"

// Test Case 5
let str1_5 = "CTCTCT"
let str2_5 = "CTCT"
print("Test Case 5: \\\\(solution.gcdOfStrings(str1_5, str2_5))")
// Expected Output: "CT"

Approaches

Approach 1: Iterative Character Appending

• Space Complexity: O(log(min(n, m))) due to recursive calls stack.
• Time Complexity: O(log(min(n, m))), akin to the time complexity of finding the GCD of two numbers.

Complexity Analysis

• Step 3: Recursively find the GCD of strings, taking the smaller string and the difference in lengths between str1 and str2.
• Step 2: If str1 equals str2, return str1 as the GCD.
• Step 1: If concatenating str1 with str2 is not equal to concatenating str2 with str1, return an empty string. This checks if str1 and str2 are composed of the same substring.

Description

• Space Complexity: O(log(min(n, m))) due to recursive calls stack.
• Time Complexity: O(log(min(n, m))), akin to the time complexity of finding the GCD of two numbers.

Complexity Analysis

• Step 3: Recursively find the GCD of strings, taking the smaller string and the difference in lengths between str1 and str2.