Sergei Golitsyn provides solutions to popular leetcode problems.

Aloha guys today we have a popular GDS problem:

Description

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: ""

Solution

To solve it we need to understand, what we want to find. We need to find greatest common part of two words, and this part should divide word on 1-N the same paths.
For example: a = ABCABC and b = ABC can be divided on a = ABC ABC and b = ABC
In the next example a = ABABAB and b = ABAB we cannot divide a on b because a = ABAB AB and ABAB != AB. That is why we should reduce divider.
We can do it iteratively, but what if we start with the rest of the longest string?
a = ABABAB after divide a has two parts common ABAB and rest AB. Let's try to use rest. Now let's try to divide longest string on short one, a = AB and b = ABAB. b will be AB AB. Hm, obviously that AB is greatest common divisor. But how can we understand it? We need to dive bit deeper and again use rest of division. a = "" and b = AB. If one of the strings is empty, another one will be our result. Wisdom, right?

Code

    public String gcdOfStrings2(String str1, String str2) {
        int l1 = str1.length();
        int l2 = str2.length();

        // Swap the parameters when needed
        if (l1 < l2){
            return gcdOfStrings(str2, str1);
        }

        // Since we swap
        if (l2 == 0){
            return str1;
        }

        // Check if str1 starts with str2
        if (!str1.startsWith(str2)) {
            return "";
        }

        return gcdOfStrings(str1.substring(l2), str2);
    }