Разбор задачи «Первый неповторяющийся символ»

1. Идея

Нужно найти первый символ строки, который встречается ровно один раз во всей строке, и вывести его позицию с нумерацией с 1.

Самая удобная идея — сделать это в два прохода:

1. Сначала посчитать, сколько раз встречается каждая буква.
2. Затем пройти по строке слева направо и найти первый символ, у которого частота равна 1.

Так как строка состоит только из строчных латинских букв, достаточно хранить частоты в массиве размера 26.

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

• Нас интересуют только буквы 'a' ... 'z', значит можно использовать массив cnt длины 26.
• Для буквы c индекс в массиве можно получить как c - 'a' в C++ или ord(c) - ord('a') в Python.
• Если во втором проходе встретился символ с частотой 1, это и есть ответ, потому что мы идём слева направо.
• Если после полного прохода такой символ не найден, нужно вывести -1.

Пример: строка abac

• частоты:
  • a — 2
  • b — 1
  • c — 1
• идём по строке:
  • a — не подходит
  • b — подходит, значит ответ 2

3. Алгоритм

1. Считать строку s.
2. Создать массив cnt из 26 нулей.
3. Для каждого символа строки увеличить соответствующий счётчик.
4. Ещё раз пройти по строке по индексам:
   • если частота текущего символа равна 1, вывести i + 1 и завершить программу.
5. Если подходящий символ не найден, вывести -1.

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

После первого прохода в массиве cnt для каждой буквы хранится точное количество её вхождений в строку.

Во втором проходе мы рассматриваем символы в том же порядке, в котором они стоят в строке. Как только встречаем символ с частотой 1, это означает:

• он встречается ровно один раз во всей строке;
• среди всех таких символов он расположен левее остальных, потому что мы идём слева направо.

Значит, первый найденный во втором проходе символ и есть первый неповторяющийся символ строки.

Если ни один символ не имеет частоту 1, ответа не существует, поэтому правильно вывести -1.

5. Сложность

• Первый проход по строке: O(n)
• Второй проход по строке: O(n)
• Итого: O(n)

Дополнительная память:

• массив из 26 чисел, то есть O(1)

6. Код на C++17

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    string s;
    cin >> s;

    vector<int> cnt(26, 0);
    for (char c : s) {
        cnt[c - 'a']++;
    }

    for (int i = 0; i < (int)s.size(); i++) {
        if (cnt[s[i] - 'a'] == 1) {
            cout << i + 1 << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
    return 0;
}

7. Код на Python 3

s = input()

cnt = [0] * 26
for c in s:
    cnt[ord(c) - ord('a')] += 1

for i in range(len(s)):
    if cnt[ord(s[i]) - ord('a')] == 1:
        print(i + 1)
        break
else:
    print(-1)