1. Идея

Нужно проверить, является ли строка палиндромом, если:

• оставить только латинские буквы;
• привести их к одному регистру;
• всё остальное игнорировать.

Самый удобный способ — не строить новую очищенную строку, а сравнивать символы с двух концов исходной строки.

Поставим два указателя:

• l — слева,
• r — справа.

Будем двигать их навстречу друг другу:

• если текущий символ не латинская буква, пропускаем его;
• когда с обеих сторон найдены буквы, сравниваем их без учёта регистра;
• если буквы различаются, ответ сразу NO;
• если указатели сошлись или пересеклись без ошибок, ответ YES.

2. Наблюдения

1. Нас интересуют только символы от A до Z и от a до z.
2. Пробелы, цифры, запятые, точки и другие знаки вообще не влияют на ответ.
3. Если после удаления лишних символов строка имеет длину 0 или 1, то это палиндром.
4. Необязательно создавать новую строку из букв. Можно проверять палиндром прямо по исходной строке, пропуская ненужные символы.
5. Такой подход работает за один проход двумя указателями.

3. Алгоритм

1. Считать всю строку целиком.
2. Завести два индекса:
   • l = 0,
   • r = len(s) - 1.
3. Пока l < r:
   • сдвигать l вправо, пока s[l] не станет латинской буквой;
   • сдвигать r влево, пока s[r] не станет латинской буквой;
   • если после этого l < r, сравнить s[l] и s[r] без учёта регистра;
   • если они не равны, вывести NO и завершить программу;
   • иначе сдвинуть l и r дальше: l += 1, r -= 1.
4. Если цикл завершился без несовпадений, вывести YES.

4. Почему это работает

Рассмотрим, что делает алгоритм.

Он всегда пропускает символы, которые по условию нужно игнорировать. Значит, для проверки остаются только латинские буквы.

Далее каждая пара сравниваемых символов — это:

• очередная буква слева среди всех значимых символов,
• очередная буква справа среди всех значимых символов.

Именно такие пары должны совпадать в палиндроме.

Сравнение идёт без учёта регистра, поэтому A и a считаются одинаковыми, как и требуется.

Если хотя бы одна такая пара не совпала, очищенная строка не может быть палиндромом, значит ответ NO.

Если все пары совпали, то последовательность всех значимых символов читается одинаково слева направо и справа налево, значит ответ YES.

5. Сложность

Каждый указатель движется только в одну сторону, и каждый символ строки рассматривается не более нескольких раз.

• Время: O(n), где n — длина строки.
• Память: O(1) дополнительной памяти.

Это подходит для ограничения до 2 * 10^5.

6. Код на C++17

#include <iostream>
#include <string>

using namespace std;

bool isLatinLetter(char c) {
    return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z');
}

char toLowerLatin(char c) {
    if ('A' <= c && c <= 'Z') return char(c - 'A' + 'a');
    return c;
}

int main() {
    string s;
    getline(cin, s);

    int l = 0;
    int r = (int)s.size() - 1;

    while (l < r) {
        while (l < r && !isLatinLetter(s[l])) l++;
        while (l < r && !isLatinLetter(s[r])) r--;

        if (l < r) {
            if (toLowerLatin(s[l]) != toLowerLatin(s[r])) {
                cout << "NO\n";
                return 0;
            }
            l++;
            r--;
        }
    }

    cout << "YES\n";
    return 0;
}

7. Код на Python 3

s = input()

def is_latin_letter(c):
    return ('a' <= c <= 'z') or ('A' <= c <= 'Z')

l = 0
r = len(s) - 1
ok = True

while l < r:
    while l < r and not is_latin_letter(s[l]):
        l += 1
    while l < r and not is_latin_letter(s[r]):
        r -= 1

    if l < r:
        if s[l].lower() != s[r].lower():
            ok = False
            break
        l += 1
        r -= 1

print("YES" if ok else "NO")