Pular para o conteúdo

Greatest Common Divisor of Strings

Fácil#gcd#string-period~15 min

A missão

Problema

Uma string t divide uma string s quando s é t escrita uma ou mais vezes em sequência. Dadas duas strings a e b, retorne a string mais longa que divide as duas, ou uma string vazia quando nenhuma string divide.

Exemplos

Input:  a = "ABCABC", b = "ABC"
Output: "ABC"
Input:  a = "ABABAB", b = "ABAB"
Output: "AB"
Por quê: AB divide as duas, enquanto ABAB não divide ABABAB
Input:  a = "LOOP", b = "POOL"
Output: ""
Por quê: edge case: as strings não compartilham nenhuma unidade de repetição

Dicas

0 / 3

Tempo-alvo
O(len(a) + len(b))
Espaço-alvo
O(len(a) + len(b))

Travou na ideia, e não no código? MDC e Euclides explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado