พิมพ์ตัวอักษรที่ไม่ซ้ำในสตริงตามลำดับใน C++

ภาพรวมปัญหา

ได้รับสตริง ต้องพิมพ์ตัวอักษรที่ไม่ซ้ำกัน (distinct characters) ตามลำดับที่ปรากฏในสตริง

ตัวอย่าง

Input: "tutorials Point"
Output: u r a l s P n

วิธีแก้ปัญหา (ใช้ Array นับความถี่)

1. สร้างอาร์เรย์ count[256] นับจำนวนครั้ง และ index[256] เก็บตำแหน่งแรก
2. เริ่มต้น: count = 0, index = n (ความยาวสตริง)
3. ลูปผ่านสตริง: เพิ่ม count, ถ้า count=1 เก็บ index, ถ้า count=2 ตั้ง index = n
4. เรียง index แล้วพิมพ์ตัวอักษรตาม index ที่ไม่เท่ากับ n

ตัวอย่างโค้ด C++

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

const int MAX_CHAR = 256;

void printDistinctCharacters(string str) {
    int n = str.length();
    int count[MAX_CHAR];
    int index[MAX_CHAR];
    
    for (int i = 0; i < MAX_CHAR; i++) {
        count[i] = 0;
        index[i] = n;
    }
    
    for (int i = 0; i < n; i++) {
        char x = str[i];
        ++count[x];
        if (count[x] == 1 && x != ' ')
            index[x] = i;
        if (count[x] == 2)
            index[x] = n;
    }
    
    sort(index, index + MAX_CHAR);
    for (int i = 0; i < MAX_CHAR && index[i] != n; i++)
        cout << str[index[i]] << " ";
}

int main() {
    string str = "tutorialsPoint";
    cout << "All distinct Characters of the string '" << str << "' are:\n";
    printDistinctCharacters(str);
    return 0;
}

ผลลัพธ์ (Output)

All distinct Characters of the string 'tutorialsPoint' are:
u r a l s P n