For two strings s and t, we say that t divides s if and only if s can be formed by concatenating one or more copies of t together (i.e., s = t + t + ... + t).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2. If no such string exists, return an empty string.
Constraints:
str1.length, str2.length
str1 and str2 consist of English uppercase letters.
The key idea behind this solution comes from a mathematical property of repeating strings. If a string x divides both str1 and str2, it means both strings are formed by repeating the same base pattern x.
Because both strings share the same repeating pattern, concatenating them in different orders should produce the same result. In other words, str1 + str2 must equal str2 + str1. If these two concatenations are different, then the strings are not built from the same repeating pattern, and no common divisor string exists.
If this condition holds, we know the strings share a common repeating pattern. The length of that pattern must divide both string lengths evenly, because each string is made by repeating the same unit. For example, if the repeating unit is "ABC", then "ABCABC" has length 6 and "ABC" has length 3, so the unit length 3 divides both lengths exactly.
Therefore, the largest possible divisor string must have a length equal to the greatest common divisor (GCD) of the two string lengths. Finally, we take the prefix of str1 with that length. This prefix represents the largest string that can repeat to form both str1 and str2.
Now, let’s look at the solution steps below:
Check whether str1 + str2 equals str2 + str1. If these two concatenations are not equal, it means there is no common divisor string, so return an empty string "". ...
For two strings s and t, we say that t divides s if and only if s can be formed by concatenating one or more copies of t together (i.e., s = t + t + ... + t).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2. If no such string exists, return an empty string.
Constraints:
str1.length, str2.length
str1 and str2 consist of English uppercase letters.
The key idea behind this solution comes from a mathematical property of repeating strings. If a string x divides both str1 and str2, it means both strings are formed by repeating the same base pattern x.
Because both strings share the same repeating pattern, concatenating them in different orders should produce the same result. In other words, str1 + str2 must equal str2 + str1. If these two concatenations are different, then the strings are not built from the same repeating pattern, and no common divisor string exists.
If this condition holds, we know the strings share a common repeating pattern. The length of that pattern must divide both string lengths evenly, because each string is made by repeating the same unit. For example, if the repeating unit is "ABC", then "ABCABC" has length 6 and "ABC" has length 3, so the unit length 3 divides both lengths exactly.
Therefore, the largest possible divisor string must have a length equal to the greatest common divisor (GCD) of the two string lengths. Finally, we take the prefix of str1 with that length. This prefix represents the largest string that can repeat to form both str1 and str2.
Now, let’s look at the solution steps below:
Check whether str1 + str2 equals str2 + str1. If these two concatenations are not equal, it means there is no common divisor string, so return an empty string "". ...