Day 16 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#1071. Greatest Common Divisor of Strings(Easy/JS)

Intro: I am a former accountant turned software engineer graduated from coding bootcamp in January 2022. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:

• Pick a leetcode problem randomly or Online Assessment from targeted companies.
• Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
• Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
• Code out the solution in LeetCode without looking at the solutions
• Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.

---

1071. Greatest Common Divisor of Strings
Difficulty: Easy Language: JavaScript

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.

---

Solution (recursion):
My first thought for getting the substring is to calculate the remainder. But I couldn't think of a good way to verify the letters from the string is in repeating state. For example, str1 = "ABABAB", str2 = "ABAB", how do we make sure str1 is not "ABCDCD" without comparing and iterating though the whole array? 'Sporkyy' from LeetCode Discussion sove this issue with one line.

var gcdOfStrings = function(str1, str2) {
      if (str1 + str2 !== str2 + str1) return '';

//This is the line I was referring to above. It made sure that
//both string has common substring and the substring repeats in
//the string (note 3)

      const gcd = (a, b) => (0 === b ? a : gcd(b, a % b));

//if length of longer string is divisible by length of shorter
//string, then the shorter string is the greatest common string
//length. If not divisible, the remainder is the greatest common
//string length. For example, given str1 = "ABCABC", str2 = "ABC",
//length of str1 is divisible by length of str1 (6/3=2), the
//greatest common string length is the shorter string 'str1'. And
//given str1 = "ABABAB", str2 = "ABAB", length of str1 is NOT
//divisible by length of str1 (6/4=1 and remainder is 2), the
//greatest common string length is the remainder 2. And the
// reatest common string length is used to extract the actual
//substring in the next step.

      return str1.substring(0, gcd(str1.length, str2.length));

//once greatest common string is found, use substring (note 2)
//to extract the substring (note 1)

};

Solution Submission detail as of 2/27/2022
(Data below could vary since there are new tests/submissions daily)

• Runtime: 68 ms
• Memory Usage: 42.8 mb

---

References:
LeetCode Problem Link
LeetCode Discussion: Sporkyy
Note 1: String length
Note 2: Substring
Note 3: Strict inequality(!==)
Note 4: Recursion in Javascript
Blog Cover Image Credit