หาคำนำหน้าร่วมยาวที่สุดระหว่างสองสตริงหลังสลับตัวอักษรสตริงที่สองใน C++

สมมติว่ามีสตริงสองตัว str1 และ str2 หาคำนำหน้าร่วม (Longest Common Prefix) ที่ยาวที่สุดระหว่างพวกเขาหลังจากทำการสลับ (Swap) บนสตริงที่สองศูนย์หรือหลายครั้ง ในแต่ละครั้ง เราสามารถสลับตัวอักษรใดๆ ก็ได้สองตัว ดังนั้นถ้า str1 = "HERE", str2 = "THERE" ผลลัพธ์จะเป็น 4 สตริงที่สองสามารถทำเป็น "HERET" ได้โดยเพียงแค่สลับตัวอักษร ดังนั้นคำนำหน้าร่วมยาวที่สุดมีความยาว 4

เรารู้ว่าเราสามารถสลับได้เฉพาะบน str2 และความยาวของคำนำหน้าควรจะมากที่สุด แนวคิดคือเดินทางผ่าน str1 และตรวจสอบว่าความถี่ของตัวอักษรปัจจุบันใน str1 เท่ากับหรือน้อยกว่าของ str2 หรือไม่ ถ้าใช่ ให้ไปต่อในสตริง a มิฉะนั้นหยุดและพิมพ์ความยาวของส่วนของ str1 จนถึงที่ตัวอักษรจับคู่ใน str2

ตัวอย่าง

#include <iostream> 
using namespace std; 

void longestPrefix(string str1, string str2) {
    int frequency[26] = {0};
    int a = str1.length();
    int b = str2.length();
    for (int i = 0; i < b; i++) {
        frequency[str2[i] - 97] += 1;
    }
    int c = 0;
    for (int i = 0; i < a; i++) {
        if (frequency[str1[i] - 97] > 0) {
            c += 1;
            frequency[str1[i] - 97] -= 1;
        } else
            break;
    }
    cout << "Length of longest common prefix: " << c;
}

int main() {
    string str1 = "here", str2 = "there";
    longestPrefix(str1, str2);
}

ผลลัพธ์

Length of longest common prefix: 4