मान लीजिए हमारे पास दो स्ट्रिंग्स str1 और str2 हैं। दूसरी स्ट्रिंग पर शून्य या अधिक स्वैप ऑपरेशन करने के बाद उनके बीच सबसे लंबा कॉमन प्रीफिक्स ढूंढना है। प्रत्येक ऑपरेशन में किन्हीं दो अक्षरों को स्वैप कर सकते हैं। उदाहरण: str1="HERE", str2="THERE" के लिए आउटपुट 4 होगा। दूसरी स्ट्रिंग को "HERET" बनाया जा सकता है, इसलिए सबसे लंबा प्रीफिक्स लंबाई 4 का है।
समाधान दृष्टिकोण
चूंकि हम केवल str2 पर स्वैप कर सकते हैं, और प्रीफिक्स की लंबाई अधिकतम करनी है। विचार: str1 को पार करें, और जांचें कि वर्तमान वर्ण की फ्रीक्वेंसी str1 में str2 में उसकी फ्रीक्वेंसी से कम या बराबर है या नहीं। यदि हां, तो आगे बढ़ें, अन्यथा ब्रेक करें और मिलान किए गए भाग की लंबाई प्रिंट करें।
C++ उदाहरण
#include <iostream>
#include <string>
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] - 'a']++;
int c = 0;
for (int i = 0; i < a; i++) {
if (frequency[str1[i] - 'a'] > 0) {
c++;
frequency[str1[i] - 'a']--;
} else
break;
}
cout << "Length of longest common prefix: " << c;
}
int main() {
string str1 = "here", str2 = "there";
longestPrefix(str1, str2);
return 0;
}
आउटपुट
Length of longest common prefix: 4
