จัดเรียง String ให้สระและพยัญชนะสลับกันใน C++

โจทย์ปัญหา

ได้รับ String ให้จัดเรียงใหม่โดยให้ สระ (Vowels) และพยัญชนะ (Consonants) สลับกัน รักษาลำดับสัมพัทธ์ภายในแต่ละกลุ่ม หากทำไม่ได้ให้แสดง "no such string" ถ้ามีหลายวิธี ให้เลือก Lexicographically Smaller

ตัวอย่าง

แนวคิดการแก้ปัญหา

1. นับจำนวนสระ (nv) และพยัญชนะ (nc)
2. ถ้า |nv - nc| > 1 → "no such string" (ไม่สามารถสลับได้)
3. แยก String เป็น vstr (สระ) และ cstr (พยัญชนะ) รักษาลำดับ
4. สร้างผลลัพธ์ตามกรณี:
   • nv > nc: เริ่มด้วยสระ → vstr[0] + alternate(cstr, vstr[1:])
   • nc > nv: เริ่มด้วยพยัญชนะ → cstr[0] + alternate(vstr, cstr[1:])
   • nv == nc: เลือกเริ่มต้นจากตัวอักษรที่น้อยกว่า (Lexicographically) ระหว่าง vstr[0] และ cstr[0]

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

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

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

string createAltStr(const string& first, const string& second, int start) {
    string result;
    for (int i = 0, j = start; j < (int)second.size(); i++, j++) {
        result += first[i];
        result += second[j];
    }
    return result;
}

string findAltStr(string str) {
    int nv = 0, nc = 0;
    string vstr, cstr;

    for (char c : str) {
        if (isVowel(c)) { nv++; vstr += c; }
        else { nc++; cstr += c; }
    }

    if (abs(nv - nc) >= 2) return "no such string";

    if (nv > nc) {
        return vstr.substr(0, 1) + createAltStr(cstr, vstr, 1);
    }
    if (nc > nv) {
        return cstr.substr(0, 1) + createAltStr(vstr, cstr, 1);
    }

    // nv == nc: เลือกเริ่มต้นจากตัวอักษรที่เล็กกว่า
    if (cstr[0] < vstr[0])
        return createAltStr(cstr, vstr, 0);
    else
        return createAltStr(vstr, cstr, 0);
}

int main() {
    cout << findAltStr("Tutorial") << endl;  // Tutorila
    cout << findAltStr("onse") << endl;      // nose
    cout << findAltStr("abc") << endl;       // abc (a=สระ, bc=พยัญชนะ)
    cout << findAltStr("aeiou") << endl;     // no such string
    return 0;
}

ผลลัพธ์

Tutorila
nose
abc
no such string

Complexity Analysis

• Time: O(n) (n = ความยาว String)
• Space: O(n) สำหรับเก็บ vstr, cstr, result

คำอธิบายเพิ่มเติม

• การรักษา Relative Order ทำให้เป็น Stable Alternating
• Lexicographically Smaller = ตัวอักษรแรกที่ต่างกัน มีค่า ASCII น้อยกว่า
• Edge Cases: String ว่าง, ทั้งหมดเป็นสระ, ทั้งหมดเป็นพยัญชนะ
• สำหรับ Unicode ต้องใช้ wstring และ iswalpha แทน