Подход к динамическому программированию или случай, который подводит жадных

У меня есть строка длины 1 <= |S| <= 100 и K (1 <= K <= 10)

Эта строка содержит digits < K и вопросительные знаки. Я хочу заменить эти вопросительные знаки на digits < K, чтобы две соседние цифры не были равны. Строка круглая, поэтому она не может быть такой: 1?1 или 11?.

Полученная строка должна быть лексикографически самой маленькой.

Пример ввода и вывода

input:
K = 4
string = ?????

output:
01012

Я пробовал жадный подход, но он терпит неудачу для некоторых неизвестных тестовых случаев. Я думаю, что для этого нужен подход dp, но он не может определить состояния, а чистый рекурсивный код не подходит по времени.

Любая помощь для подхода dp или сложные тестовые примеры, которые не позволяют жадным?

Спасибо,