Algorithm

Problem Name: 1071. Greatest Common Divisor of Strings

Problem Link: https://leetcode.com/problems/greatest-common-divisor-of-strings/
 

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

 

Constraints:

  • 1 <= str1.length, str2.length <= 1000
  • str1 and str2 consist of English uppercase letters.

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public String gcdOfStrings(String str1, String str2) {
    if (str1.length() < str2.length()) {  
      return gcdOfStrings(str2, str1); 
    } else if (!str1.startsWith(str2)) {
      return "";
    } else if (str2.isEmpty()) { 
      return str1;
    } else { 
      return gcdOfStrings(str1.substring(str2.length()), str2); 
    }
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
str1 = "ABCABC", str2 = "ABC"

Output

x
–
+
cmd
"ABC"

#2 Code Example with Javascript Programming

Code - Javascript Programming


const gcdOfStrings = function(str1, str2) {
  let res = "";

  if (str1[0] !== str2[0]) return res;
  if (str1[str1.length - 1] !== str2[str2.length - 1]) return res;
  let s = str1[0];
  let e = str1[str1.length - 1];

  let loopStr = str1.length > str2.length ? str2 : str1;
  for (let i = 1, len = loopStr.length; i  <  len; i++) {
    if (loopStr[i] !== e) continue;
    let tmp = loopStr.slice(0, i + 1);
    let ok1 = false;
    let ok2 = false;
    let t1 = "";
    let t2 = "";
    while (t1.length  <  str1.length) {
      t1 += tmp;
      if (t1 === str1) {
        ok1 = true;
        break;
      }
    }
    while (t2.length  <  str2.length) {
      t2 += tmp;
      if (t2 === str2) {
        ok2 = true;
        break;
      }
    }

    if (ok1 && ok2 && tmp.length > res.length) res = tmp;
  }

  return res;
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
str1 = "ABCABC", str2 = "ABC"

Output

x
–
+
cmd
"ABC"

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if len(str1) == len(str2):
            return str1 if str1==str2 else ''
        else:
            if len(str1) < len(str2):
                str1,str2 = str2,str1
            if str1[:len(str2)] == str2:
                return self.gcdOfStrings(str1[len(str2):],str2)
            else:
                return ''
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
str1 = "ABABAB", str2 = "ABAB"

Output

x
–
+
cmd
"AB"

#4 Code Example with C# Programming

Code - C# Programming


using System.Text;

namespace LeetCode
{
    public class _1071_GreatestCommonDivisorOfStrings
    {
        public string GcdOfStrings(string str1, string str2)
        {
            if (str1 == str2) return str1;
            if (str1.Length > str2.Length) return GcdOfStrings(str2, str1);

            var i = 1;
            while (i  < = str1.Length)
            {
                var length = str1.Length / i;
                if ((str1.Length % length == 0) && (str2.Length % length == 0))
                {
                    var sb1 = new StringBuilder();
                    var sb2 = new StringBuilder();

                    var result = str1.Substring(0, length);

                    var x1 = str1.Length / length;
                    for (int j = 0; j  <  x1; j++)
                        sb1.Append(result);
                    var x2 = str2.Length / length;
                    for (int j = 0; j  <  x2; j++)
                        sb2.Append(result);

                    if ((str1 == sb1.ToString()) && (str2 == sb2.ToString()))
                        return result;
                }
                i++;
            }

            return string.Empty;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
str1 = "ABABAB", str2 = "ABAB"

Output

x
–
+
cmd
"AB"
Advertisements

Demonstration

Previous
#1061 Leetcode Lexicographically Smallest Equivalent String Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1072 Leetcode Flip Columns For Maximum Number of Equal Rows Solution in C, C++, Java, JavaScript, Python, C# Leetcode