algoadvance

Leetcode 1071. Greatest Common Divisor of Strings

Problem Statement

You are given two strings str1 and str2. You need to determine the largest string x such that x divides both str1 and str2. A string a is said to divide string b if b is formed by concatenating a one or more times.

Clarifying Questions

1. What constitutes a string dividing another string?
   • A string a divides string b if and only if b is formed by concatenating a one or more times.
2. What are the lengths of the input strings?
   • The lengths of str1 and str2 are not specified but we can assume that they are reasonable for typical interview problems.
3. Are there any constraints on the content of the strings?
   • The strings can consist of any characters, but in practical terms, it’s often alphabetic characters.

Strategy

1. Check for Validity:
   • If str1 + str2 is not equal to str2 + str1, there is no common divisor string. This comes from the observation that the concatenation in different orders should be equal if there is some common string x that can divide both strings.
2. GCD of Lengths:
   • Compute the greatest common divisor (GCD) of the lengths of str1 and str2 using the Euclidean algorithm.
   • The length of the greatest common divisor string must be the GCD of the lengths of str1 and str2.
3. Extract and Verify:
   • Take the substring of str1 from 0 to the length of the GCD.
   • Check if this substring divides both str1 and str2.

Code

Here’s the Java implementation of the above strategy:

public class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        int gcdLength = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdLength);
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.gcdOfStrings("ABCABC", "ABC")); // Output: "ABC"
        System.out.println(sol.gcdOfStrings("ABABAB", "ABAB")); // Output: "AB"
        System.out.println(sol.gcdOfStrings("LEET", "CODE"));   // Output: ""
    }
}

Time Complexity

• GCD Calculation: This typically runs in O(log(min(a, b))) time due to the Euclidean algorithm.
• String Addition and Equality Check: These operations are O(n) where n is the total combined length of the strings.
• Substring Extraction: This can be considered O(1) since it’s directly creating a new string from the calculated GCD length, which is very efficient.

Overall, the time complexity of the implemented solution is O(n) where n is the combined length of the two strings.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?