Tìm ký tự không lặp lại đầu tiên chỉ duyệt chuỗi một lần C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ tìm ký tự đầu tiên không bị lặp lại (non-repeating) trong chuỗi, chỉ cần duyệt chuỗi một lần để thống kê tần suất.

Ví dụ

Input: "tutorialspoint"
Output: u

Ý tưởng

Sử dụng map<char, array<int, 2>> để lưu: [tần suất, chỉ số xuất hiện đầu tiên]. Duyệt chuỗi một lần để điền map, sau đó duyệt map tìm ký tự có tần suất = 1 và chỉ số nhỏ nhất.

Mã nguồn ví dụ

#include <bits/stdc++.h>
#include <map>
using namespace std;

void findDistinctCharacters(string random_string) {
    map<char, int[2]> chars;
    for (int i = 0; i < random_string.size(); ++i) {
        chars[random_string[i]][0]++; // tần suất
        chars[random_string[i]][1] = i; // chỉ số
    }
    int char_index = INT_MAX;
    for (auto item : chars) {
        if (item.second[0] == 1) {
            char_index = min(char_index, item.second[1]);
        }
    }
    cout << random_string[char_index];
}

int main() {
    findDistinctCharacters("tutorialspoint");
    return 0;
}

Kết quả đầu ra

u

Kết luận

Ký tự 'u' xuất hiện 1 lần ở vị trí sớm nhất. Giải pháp O(n log n) do dùng map (có thể O(n) với unordered_map). Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.