Самая короткая строка, образованная объединением строк A x раз и B y раз таким образом, что n(A)*x = n(B)*y

Опубликовано: 20 Сентября, 2022

Имея две строки A и B , задача состоит в том, чтобы найти кратчайшую строку, кратную как A , так и B . Говорят, что строка X кратна строке Y , если строка X может быть образована конкатенацией нескольких вхождений строки Y.

Пример:

Input: A = “aaa”, B= “aa”
Output: aaaaaa
Explanation: Multiplying A two times and B three times will result in aaaaaa

Input: A=”cold”, B =”old”
Output: -1

Подход: Данная задача может быть решена на основе наблюдения, что длина наименьшей строки, которая может быть кратна обеим строкам A и B , должна быть равна НОК длины A и длины B . Таким образом, данная проблема может быть решена с помощью следующих шагов:

  • Создайте переменную lcm , которая хранит значение LCM длины A и длины B .
  • Создайте строку C , которая формируется после объединения строки A , lcm / (длина A) раз.
  • Точно так же создайте строку D , которая формируется после объединения строки B , lcm / (длина B) раз.
  • Проверьте, равны ли строки C и D. Если они есть, выведите любой из них, иначе выведите -1 .

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ