Chuỗi xen kẽ nguyên âm và phụ âm trong C++

Cho một chuỗi, sắp xếp lại ký tự sao cho nguyên âm và phụ âm xen kẽ nhau. Nếu không thể → in "no such string". Giữ nguyên thứ tự nguyên âm giữa chúng và phụ âm giữa chúng. Nếu nhiều chuỗi thỏa mãn → chọn chuỗi nhỏ nhất theo từ điển (lexicographically smaller).

Ví dụ

Input: Tutorial → Output: Tutorila
Input: onse → Output: nose
(Có 2 kết quả: "nose" và "ones", "nose" nhỏ hơn từ điển)

Giải pháp:

• Đếm số nguyên âm (nv) và phụ âm (nc).
• Nếu |nv - nc| ≥ 2 → "Not Possible".
• Nếu nv > nc: in nguyên âm đầu tiên, đệ quy phần còn lại.
• Nếu nc > nv: in phụ âm đầu tiên, đệ quy phần còn lại.
• Nếu bằng nhau: so sánh nguyên âm đầu và phụ âm đầu, in cái nhỏ hơn trước.

Chương trình C++

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

bool isVowel(char ch1) {
    return (ch1=='a'||ch1=='e'||ch1=='i'||ch1=='o'||ch1=='u');
}

string createAltStr(string str1, string str2, int start1, int l1) {
    string finalStr1 = "";
    for (int i=0, j=start1; j<l1; i++, j++)
        finalStr1 = (finalStr1 + str1.at(i)) + str2.at(j);
    return finalStr1;
}

string findAltStr(string str3) {
    int nv1 = 0, nc1 = 0;
    string vstr1 = "", cstr1 = "";
    int l1 = str3.size();
    for (int i=0; i<l1; i++) {
        char ch1 = str3.at(i);
        if (isVowel(ch1)) { nv1++; vstr1 += ch1; }
        else { nc1++; cstr1 += ch1; }
    }
    if (abs(nv1-nc1) >= 2) return "no such string";
    if (nv1 > nc1) return (vstr1.at(0) + createAltStr(cstr1, vstr1, 1, nv1));
    if (nc1 > nv1) return (cstr1.at(0) + createAltStr(vstr1, cstr1, 1, nc1));
    if (cstr1.at(0) < vstr1.at(0))
        return createAltStr(cstr1, vstr1, 0, nv1);
    return createAltStr(vstr1, cstr1, 0, nc1);
}

int main() {
    string str3 = "Tutorial";
    cout << findAltStr(str3);
    return 0;
}

Kết quả

Tutorila

Độ phức tạp thời gian: O(n), n là độ dài chuỗi.