Algorithm
LeetCode 75
Greatest Common Divisor of Strings

1071. Greatest Common Divisor of Strings

Tags

  • Math
  • String

Link

https://leetcode.com/problems/greatest-common-divisor-of-strings/?envType=study-plan-v2&envId=leetcode-75 (opens in a new tab)

Question

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 thatx 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.

Answer

JavaScript

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function (str1, str2) {
  // Helper function to compute the GCD of two numbers
  function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
  }
 
  // Check if str1 + str2 equals str2 + str1
  if (str1 + str2 !== str2 + str1) {
    return ""; // No common divisor string
  }
 
  // Find the GCD of the lengths of the two strings
  const gcdLength = gcd(str1.length, str2.length);
 
  // The GCD string will be the substring of str1 from 0 to gcdLength
  return str1.substring(0, gcdLength);
};
/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function (str1, str2) {
  let len1 = str1.length;
  let len2 = str2.length;
  let minLen;
 
  let join1 = str1.concat(str2);
  let join2 = str2.concat(str1);
 
  if (join1 !== join2) {
    return "";
  }
 
  let gcd = 1;
 
  if (len1 > len2) {
    minLen = len2;
  } else {
    minLen = len1;
  }
 
  for (let i = 2; i <= minLen; i++) {
    if (len1 % i == 0 && len2 % i == 0) {
      gcd = i;
    }
  }
 
  return str1.slice(0, gcd);
};
/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function (str1, str2) {
  let minLength = Math.min(str1.length, str2.length);
  if (str1 + str2 !== str2 + str1) {
    return "";
  }
  for (let i = minLength; i > 0; i--) {
    if (str1.length % i === 0 && str2.length % i === 0) {
      return str1.substring(0, i);
    }
  }
};
Find the Highest AltitudeIncreasing Triplet Subsequence