মনে করুন আমাদের দুটি স্ট্রিং str1 এবং str2 আছে। দ্বিতীয় স্ট্রিং-এ শূন্য বা অধিক অপারেশন করার পর তাদের মধ্যকার সবচেয়ে বড় কমন প্রিফিক্স বের করতে হবে। প্রতিটি অপারেশনে, আমরা যেকোনো দুটি অক্ষর сваপ করতে পারি। তাই যদি str1 = "HERE", str2 = "THERE" হয়, তবে আউটপুট হবে 4। দ্বিতীয় স্ট্রিংটি "HERET" বানানো যাবে ক্যারেক্টারগুলো сваপ করে। তাই সবচেয়ে বড় প্রিফিক্সের দৈর্ঘ্য 4।
যেহেতু আমরা শুধু str2-এ স্বাপ করতে পারি। এবং প্রিফিক্সের দৈর্ঘ্য সর্বোচ্চ করতে হবে। তাই আইডিয়াটি হল str1 ট্রাভার্স করা, এবং চেক করা যে str1-এ বর্তমান ক্যারেক্টারের ফ্রিকোয়েন্সি str2-এ তার ফ্রিকোয়েন্সির সমান বা কম কিনা। যদি হ্যাঁ, তবে str1-এ آگে বড়ুন, অন্যথায় ব্রেক করুন এবং 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
