Greatest Common Divisor of Strings

For strings S and T, we say "T divides S" if and only if S = T + ... + T (T concatenated with itself 1 or more times)

Return the largest string X such that X divides str1 and X divides 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: ""

Note:

1 <= str1.length <= 1000

1 <= str2.length <= 1000

str1[i] and str2[i] are English uppercase letters.

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.String
{
 class GcdOfStringsSln
 {
 public void execute()
 {
 var str1 = "ABABAB";
 var str2 = "ABAB";
 var res = GcdOfStrings(str1, str2);
 }

 public string GcdOfStrings(string str1, string str2)
 {
 if (str1 + str2 != str2 + str1) return "";
 if (str1 == str2) return str1;
 int len1 = str1.Length;
 int len2 = str2.Length;

 while (len2 > 0)
 {
 int temp = len2;
 len2 = len1 % len2;
 len1 = temp;
 }

 return str1.Substring(0, len1);
 }
 }
}

Time Complexity: O(m+n) where m and n are the lengths of the string.

Space Complexity: O(1)