Greatest Common Divisor of Strings
Greatest Common Divisor of Strings is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Repeated Substring Pattern Detection subpattern.
Problem statement
A string x divides another string y when y can be formed by concatenating one or more copies of x. A common divisor string of str1 and str2 must divide both parameters.
Return the longest string that divides both str1 and str2. If no non-empty string has this property, return the empty string.
Example 1:
Input: str1 = "XYZXYZXYZ", str2 = "XYZXYZ" Output: "XYZ" Explanation: "XYZ" repeated three times forms str1 and repeated twice forms str2; no longer common repeating block exists.
Example 2:
Input: str1 = "ABCA", str2 = "AB" Output: "" Explanation: The two strings are not composed of repetitions of the same non-empty block, so no common divisor string exists.
Example 3:
Input: str1 = "KLMKLM", str2 = "KLMKLM" Output: "KLMKLM" Explanation: A string divides itself, and the entire input is the longest possible common divisor.
Constraints:
- 1 <= str1.length <= 10^3 - 1 <= str2.length <= 10^3 - str1 and str2 contain only uppercase English letters - str1 and str2 are non-empty strings
Topics and companies
Topics: String, Math, Number Theory.
How to practise Greatest Common Divisor of Strings on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(|str1| + |str2|) time and O(|str1| + |str2|) auxiliary space space.
Open Greatest Common Divisor of Strings in the code editor, or read the Greatest Common Divisor of Strings editorial for a worked solution with its approach and complexity analysis.
Where Greatest Common Divisor of Strings sits in the DSA pattern sheet
- String Manipulation Patterns pattern guide
- Repeated Substring Pattern Detection subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Greatest Common Divisor of Strings
Other problems that use the same Repeated Substring Pattern Detection and String Manipulation Patterns techniques:
- Repeated Substring Pattern — Easy, same subpattern
- Add Strings — Easy, same pattern
- Excel Sheet Column Title — Easy, same pattern
- Find Beautiful Indices in the Given Array II — Hard, same pattern
- Find the Index of the First Occurrence in a String — Easy, same pattern
- Integer to Roman — Medium, same pattern