Ước Chung Lớn Nhất Của Chuỗi (GCD of Strings) Trong Python

Cho 2 chuỗi str1, str2. Chuỗi A chia hết cho B nếu A = B + B + ... + B (nối B nhiều lần). Tìm chuỗi dài nhất chia hết cho cả str1 và str2 (GCD của chuỗi).

Ví dụ: str1="ABABAB", str2="ABAB" → GCD = "AB" (vì ABABAB = AB×3, ABAB = AB×2).

Thuật toán

1. Nếu str1 + str2 != str2 + str1 → không có GCD chung → trả về ""
2. Độ dài GCD = gcd(len(str1), len(str2)) (ước chung lớn nhất của độ dài)
3. Trả về str1[:gcd_len]

Lý do: Nếu 2 chuỗi có GCD chung, chúng phải được xây từ cùng một chuỗi cơ sở. Thứ tự nối không quan trọng → str1+str2 == str2+str1.

Ví dụ (Python)

import math

class Solution(object):
    def gcdOfStrings(self, str1, str2):
        # Kiểm tra có GCD chung không
        if str1 + str2 != str2 + str1:
            return ""
        
        # Độ dài GCD = gcd độ dài 2 chuỗi
        gcd_len = math.gcd(len(str1), len(str2))
        return str1[:gcd_len]

ob1 = Solution()
print(ob1.gcdOfStrings("ABABAB", "ABAB"))  # "AB"
print(ob1.gcdOfStrings("ABCABC", "ABC"))   # "ABC"
print(ob1.gcdOfStrings("LEET", "CODE"))    # ""

Độ phức tạp

• Thời gian: O(n + m) (nối chuỗi + gcd)
• Không gian: O(n + m) (chuỗi nối tạm)

Đầu vào / Đầu ra

Input:  str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Input:  str1 = "LEET", str2 = "CODE"
Output: ""