Поиск палиндрома

Необходимо разработать программу, которая реализует поиск палиндрома с использованием рекурсии. Палиндром - слово или фраза, которые одинаково читаются слева направо и справа налево
Пользователем на вход подается строка, сгенерированная случайным образом (не более 30 символов, поддержка русского и английского языков, а также служебных символов ',.~`/?!@#$%^&*()_+ {}[]:;\| )
Задача - найти максимальный палиндром во входной строке. Реализация поиска палиндрома должна быть с использованием рекурсии. Результатом работы программы будет
Найденный максимальный палиндром
Какие символы и на каких позициях должны быть удалены для получения максимального палиндрома
Время работы алгоритма
Если палиндромов несколько одинаковой длины, то программа выводит первый полученный палиндром
Ограничение - нельзя использовать функции строк и любые функции, позволяющие определить палиндром, подстроку в строке, длину строки и пр. Можно использовать функции scanf, printf (или их аналоги)
Пример
На вход подается строка 1q2wr3t5a3gw2plmq
Выходное значение: 1q2w353w2q1
Результат должен выглядеть следующим образом
1q2w353w2q
5 - r, 7 - t, 9 - a, 11 - g, 14 - p, 15 - l, 16 -
Затраченное время: 0,0034576.