Максимальное количество ходов для достижения целевого символа в циклической строке

Дана циклическая строка S длины N , состоящая всего из трех символов ' a ', ' b ' и ' c '. Также даны два символа, начальный символ ( ic ) и конечный символ ( fc ). задача состоит в том, чтобы найти максимальное расстояние от ic до ближайшего fc .

Примеры:

Input: s = “caacb”, ic = ‘c’, fc = ‘a’
Output: 3
Explanation: The initial character is ‘c’ and final character is ‘a’, so there are two options: either ‘a’ will be on just after 1 move(if we choose s[0] as ic), or after 3 moves (if we choose s[3] as ic). So, the answer is equal to 3 — which is the maximum possible number of moves to reach from ic to fc.

Input: s = “cccabbbab”, ic = ‘b’, fc = ‘a’
Output: 4

Подход: Чтобы решить проблему, следуйте следующей идее:

For each traverse of ic in the string, we need to find the rightmost fc distance, and then find the maximum distance between ic and the nearest fc. 

Следуйте инструкциям, чтобы решить проблему:

• Чтобы избавиться от цикличности, мы можем написать строку S дважды и для каждой клетки ic из первой половины найти ближайшую fc справа, тем самым мы решили проблему с цикличностью.
• И теперь мы можем просто пройти по этой строке справа налево и сохранить индекс последнего вхождения fc .
• Если в следующий раз мы встретим ic , то обновим ответ как ans = max(ans, last – i) .
• Где last — ближайший из пройденных fc , а i — текущий.

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

Временная сложность: O(N)
Вспомогательное пространство: O(N), так как мы соединяем одну и ту же строку с самой собой

Статьи по Теме:

• Введение в String — учебные пособия по структурам данных и алгоритмам