แปลงสตริงให้มีเฉพาะตัวอักษรที่ไม่ซ้ำกันใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมแปลงสตริงที่กำหนดให้มีเฉพาะตัวอักษรที่ไม่ซ้ำกัน (distinct characters)

สำหรับนี้ เราจะได้รับสตริงหนึ่ง งานของเราคือท่องผ่านสตริงและแทนที่ตัวอักษรที่ซ้ำด้วยตัวอักษรสุ่มที่ยังไม่มีในสตริง

โปรแกรมตัวอย่าง

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

// เก็บตัวอักษรที่ไม่ซ้ำในสตริง
int calculate_zero(int i, int occurrences[]) {
    while (i < 26) {
        // ถ้ามีแค่ครั้งเดียว
        if (occurrences[i] == 0)
            return i;
        i++;
    }
    // ถ้าทุกตัวซ้ำหมด
    return -1;
}

// พิมพ์สตริงที่แก้ไขแล้ว
string print_modified(string str) {
    int n = str.length();
    // ถ้าแปลงไม่ได้
    if (n > 26)
        return "-1";
    string ch = str;
    int i, occurrences[26] = {0};
    // นับความถี่
    for (i = 0; i < n; i++)
        occurrences[ch[i] - 'a']++;
    int index = calculate_zero(0, occurrences);
    for (i = 0; i < n; i++) {
        // แทนที่ตัวอักษร
        if (occurrences[ch[i] - 'a'] > 1) {
            occurrences[ch[i] - 'a']--;
            ch[i] = (char)('a' + index);
            occurrences[index] = 1;
            // ไปตัวถัดไป
            index = calculate_zero(index + 1, occurrences);
        }
    }
    cout << ch << endl;
    return ch;
}

int main() {
    string str = "tutorialspoint";
    print_modified(str);
}

ผลลัพธ์

bucdrealspoint