मान लीजिए हमारे पास N स्ट्रिंग्स की एक सरणी A है। प्रत्येक स्ट्रिंग लोअरकेस अक्षरों से बनी है, सभी की लंबाई समान है। अब, हम डिलीशन सूचकांकों का कोई भी समुच्चय चुन सकते हैं, और प्रत्येक स्ट्रिंग के लिए, हम उन सूचकांकों पर सभी वर्णों को हटा देंगे। अब मान लीजिए हमने डिलीशन सूचकांकों का एक समुच्चय D लिया है जैसे कि डिलीशन के बाद, अंतिम सरणी का हर तत्व लेक्सिकोग्राफिक क्रम में है।
स्पष्टता के लिए, A[0] लेक्सिकोग्राफिक क्रम में है (यानी A[0][0] <= A[0][1] <= ... <= A[0][n-1]), A[1] लेक्सिकोग्राफिक क्रम में है, और इसी तरह। (यहां n स्ट्रिंग्स का आकार है)। हमें D के आकार का न्यूनतम संभव मान ढूंढना है।
उदाहरण के लिए, यदि इनपुट ["cbcdb","ccbxc"] है, तो आउटपुट 3 होगा।
हल करने का दृष्टिकोण
यह कॉलम पर सबसे लंबी बढ़ती हुई उपअनुक्रम (LIS) समस्या है:
lis[i] = कॉलम i पर समाप्त होने वाली सबसे लंबी वैध कॉलम अनुक्रम की लंबाई
प्रत्येक कॉलम जोड़ी (j, i) के लिए जहां j < i, जांचें कि क्या सभी पंक्तियों के लिए A[k][j] <= A[k][i]
यदि वैध है, तो lis[i] = max(lis[i], lis[j] + 1) अपडेट करें
उत्तर = कुल_कॉलम - अधिकतम_LIS_लंबाई
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minDeletionSize(vector<string>& A){
int ret = 0;
int n = A.size();
int m = A[0].size();
vector<int> lis(m + 1, 1);
for (int i = 0; i < m; i++) {
for (int j = 0; j < i; j++) {
bool ok = true;
for (int k = 0; k < n; k++) {
if (A[k][j] > A[k][i]) {
ok = false;
break;
}
}
if (ok) {
lis[i] = max(lis[j] + 1, lis[i]);
ret = max(ret, lis[i]);
}
}
}
if (ret == 0) return m - 1;
return m - ret;
}
};
int main(){
Solution ob;
vector<string> v = {"cbcdb","ccbxc"};
cout << (ob.minDeletionSize(v));
return 0;
}
इनपुट
{"cbcdb","ccbxc"}
आउटपुट
3