In vị trí sắp xếp ký tự tạo thành palindrome trong C

Cho chuỗi str độ dài n. In ra vị trí của từng ký tự sao cho chuỗi tạo thành palindrome, nếu không thể thì in "No palindrome".

Palindrome là gì?

Palindrome là từ hoặc chuỗi ký tự đọc xuôi và ngược đều giống nhau, ví dụ: MADAM, racecar.

Bài toán này yêu cầu in ra thứ tự chỉ số (bắt đầu từ 1) để sắp xếp lại chuỗi thành palindrome. Ví dụ: chuỗi "tinni" có thể sắp thành "intni" hoặc "nitin", kết quả chỉ số là 2 3 1 4 5 hoặc 3 2 1 5 4.

Ví dụ

Input: str = "baa"      Output: 2 1 3
Input: str = "tinni"    Output: 2 3 1 4 5

Thuật toán

void printPalindromePos(string &str)
BẮT ĐẦU
BƯỚC 1: KHAI BÁO vector pos[MAX]
BƯỚC 2: GÁN n = ĐỘ DÀI str
BƯỚC 3: VỚI i = 0 ĐẾN i < n, i++
    pos[str[i]].push_back(i+1)
KẾT THÚC VỚI
BƯỚC 4: oddCount = 0
BƯỚC 5: KHAI BÁO oddChar
BƯỚC 6: VỚI i = 0 ĐẾN i < MAX, i++
    NẾU pos[i].size() % 2 != 0 THÌ
        oddCount++
        oddChar = i
    KẾT THÚC NẾU
KẾT THÚC VỚI
BƯỚC 7: NẾU oddCount > 1 THÌ IN "NO PALINDROME"
BƯỚC 8: VỚI i = 0 ĐẾN i < MAX, i++
    mid = pos[i].size() / 2
    VỚI j = 0 ĐẾN j < mid, j++
        IN pos[i][j]
    KẾT THÚC VỚI
KẾT THÚC VỚI
BƯỚC 9: NẾU oddCount > 0 THÌ
    last = pos[oddChar].size() - 1
    IN pos[oddChar][last]
    pos[oddChar].pop_back()
KẾT THÚC NẾU
BƯỚC 10: VỚI i = MAX-1 ĐẾN i >= 0, i--
    count = pos[i].size()
    VỚI j = count/2 ĐẾN j < count, j++
        IN pos[i][j]
KẾT THÚC

Chương trình C++ ví dụ

#include <bits/stdc++.h>
using namespace std;
const int MAX = 256;

void printPalindromePos(string &str) {
    vector pos[MAX];
    int n = str.length();
    for (int i = 0; i < n; i++)
        pos[str[i]].push_back(i+1);

    int oddCount = 0;
    char oddChar;
    for (int i = 0; i < MAX; i++) {
        if (pos[i].size() % 2 != 0) {
            oddCount++;
            oddChar = i;
        }
    }
    if (oddCount > 1) {
        cout << "NO PALINDROME";
        return;
    }
    for (int i = 0; i < MAX; i++) {
        int mid = pos[i].size() / 2;
        for (int j = 0; j < mid; j++)
            cout << pos[i][j] << " ";
    }
    if (oddCount > 0) {
        int last = pos[oddChar].size() - 1;
        cout << pos[oddChar][last] << " ";
        pos[oddChar].pop_back();
    }
    for (int i = MAX-1; i >= 0; i--) {
        int count = pos[i].size();
        for (int j = count/2; j < count; j++)
            cout << pos[i][j] << " ";
    }
}

int main() {
    string s = "tinni";
    printPalindromePos(s);
    return 0;
}

Kết quả

2 3 1 4 5