Реши задание на изображении

Краткий ответ

Строку \(t\) целиком строить не нужно. Для любой пары символов \((c,d)\):

\[ count_t(c,d)=k\cdot count_s(c,d)+(k-1)\cdot [c=s[-1]\text{ и }d=s[0]] \]

где \(count_s(c,d)\) — сколько раз биграмма \(cd\) встречается внутри одной копии строки \(s\).
Затем выбираем максимальное значение; при равенстве — лексикографически наименьшую пару.

Почему так

Строка \(t\) состоит из \(k\) одинаковых копий \(s\).

Биграммы в \(t\) бывают двух видов:

1. Внутри одной копии.
   Каждая биграмма строки \(s\) встречается в каждой из \(k\) копий, поэтому даёт \(k\cdot count_s(c,d)\) вхождений.

2. На границе между копиями.
   Такая граница выглядит одинаково: \[ s[-1]s[0] \] Копий \(k\), значит границ между ними \(k-1\). Поэтому биграмма \(s[-1]s[0]\) дополнительно встречается \(k-1\) раз.

Больше никаких вариантов нет.

Проверка на первом примере

\[ s=\text{abab},\quad k=2,\quad t=\text{abababab} \]

Внутри \(s\):

• \(ab\) встречается 2 раза: \(abab\), значит в \(t\): \(2\cdot2=4\);
• \(ba\) встречается 1 раз, значит \(1\cdot2=2\), плюс граница между копиями: \(b|a\), ещё 1 раз. Итого \(ba=3\).

Максимум: \(ab\), 4 раза.

Код на Python

import sys

def solve():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    s = data[2]

    # count_s[x][y] — количество биграмм из символов x и y внутри одной s
    count_s = [[0] * 26 for _ in range(26)]

    for i in range(n - 1):
        x = ord(s[i]) - ord('a')
        y = ord(s[i + 1]) - ord('a')
        count_s[x][y] += 1

    last = ord(s[-1]) - ord('a')
    first = ord(s[0]) - ord('a')

    best_count = -1
    answer = ""

    # Перебираем пары в лексикографическом порядке: aa, ab, ..., zz
    for x in range(26):
        for y in range(26):
            cur = count_s[x][y] * k

            if x == last and y == first:
                cur += k - 1

            # Строгое > сохраняет первую, то есть лексикографически наименьшую
            if cur > best_count:
                best_count = cur
                answer = chr(ord('a') + x) + chr(ord('a') + y)

    print(answer)
    print(best_count)


if __name__ == "__main__":
    solve()

Сложность: \(O(n + 26^2)\), то есть фактически \(O(n)\).
Память: \(O(26^2)\).