Что спрашивают
Фрагмент должен начинаться и заканчиваться одинаковыми заглавными буквами, а между ними содержать хотя бы одну цифру и больше никаких букв. Нужно максимизировать количество цифр. При равенстве выбирается меньший индекс начала, нумерация — с нуля.
В ответе требуется индекс, а не длина. Ведущие нули в последовательности цифр допустимы: здесь не проверяется запись отдельного числа.
Приём решения
Достаточно рассматривать соседние буквы исходной строки. Если между двумя выбранными буквами есть третья, фрагмент уже нарушает условие. Запоминаем последнюю встреченную букву и её позицию.
При очередной букве на позиции i сравним её с предыдущей. Между ними i - last_index - 1 символов; поскольку других букв нет, все они цифры. Равные буквы и строго положительная длина дают кандидата.
- Идите по строке, пропуская цифры до следующей буквы.
- Сравните новую букву с последней и вычислите число цифр между ними.
- Обновите ответ только при строгом увеличении количества цифр.
- После проверки всегда сохраните новую букву как последнюю.
Строгое сравнение автоматически сохраняет более раннее начало при равенстве: соседние пары рассматриваются слева направо. Новая граничная буква может одновременно завершать предыдущий фрагмент и начинать следующий, поэтому такие пересечения не пропускаются.
Каждая буква участвует не более чем в двух соседних парах. Время — O(n), дополнительная память — O(1).
Разбор на примере
Ввод
7A01A234A9B55BC678C
Вывод
4
| Соседние буквы, индексы | Цифр между ними | Лучшее начало |
|---|---|---|
| A: 1 и 4 | 2 | 1 |
| A: 4 и 8 | 3 | 4 |
| A: 8 и B: 10 | 1 | Буквы разные |
| B: 10 и 13 | 2 | 4 |
| C: 14 и 18 | 3 | Равенство: сохраняем 4 |
Фрагменты A01A и A234A используют общую букву A. Второй содержит три цифры и начинается на позиции 4. Позже C678C даёт столько же цифр, но начинается дальше, поэтому ответ остаётся 4. Пару разных букв A и B не рассматриваем как подходящий фрагмент.
Код на Python и C++
Гарантия условия обеспечивает существование кандидата. Начальное best_digits равно нулю, поэтому соседние буквы без цифр не засчитываются.
import sys
def solve(s):
last_letter = None
last_index = -1
best_digits = 0
answer = 0
for i, ch in enumerate(s):
if 'A' <= ch <= 'Z':
digits = i - last_index - 1
if ch == last_letter and digits > best_digits:
best_digits = digits
answer = last_index
last_letter = ch
last_index = i
return answer
if __name__ == '__main__':
print(solve(sys.stdin.readline().rstrip('\r\n')))
<iostream>
<string>
using namespace std;
int solve(const string& s) {
char last_letter = 0;
int last_index = -1, best_digits = 0, answer = 0;
for (int i = 0; i < (int)s.size(); i++) {
char ch = s[i];
if ('A' <= ch && ch <= 'Z') {
int digits = i - last_index - 1;
if (ch == last_letter && digits > best_digits) {
best_digits = digits;
answer = last_index;
}
last_letter = ch;
last_index = i;
}
}
return answer;
}
int main() {
string s;
getline(cin, s);
if (!s.empty() && s.back() == '\r')
s.pop_back();
cout << solve(s) << endl;
}
Типичные ошибки
- Разрешить другие буквы внутри
В фрагменте должны быть ровно две буквы. Сравнивайте соседние буквы исходной строки, а не любые одинаковые.
- Пропустить общую граничную букву
После проверки пары правая буква становится левой для следующей. Непересекающийся поиск регулярным выражением может потерять такую пару.
- Обновлять индекс при равной длине
Тогда победит более поздний фрагмент. Для выбора раннего начала используйте строгое увеличение количества цифр.
- Перейти к нумерации с единицы
Условие явно задаёт индексы с нуля. Возвращайте сохранённую позицию без прибавления единицы.