সমস্যা বিবরণ
Nটি স্ট্রিংয়ের অ্যারে A দেওয়া থাকলে, কিছু কলাম ডিলিট করে প্রতিটি স্ট্রিংকে লেক্সিকোগ্রাফিক্যালি সর্টেড বানাতে হবে। ন্যূনতম কতটি কলাম ডিলিট করতে হবে তা বের করতে হবে।
উদাহরণ
A = ["cbcdb","ccbxc"] → আউটপুট = 3
সমাধান পদ্ধতি
- লংগেস্ট ইনক্রিজিং সিকোয়েন্স (LIS) কনসেপ্ট ব্যবহার করা হয়।
- lis[i] = i-তম কলাম শেষে সর্বোচ্চ কতটি কলাম রাখা যায়।
- দুই কলাম j এবং i (j < i) রাখা যাবে যদি সব স্ট্রিংয়ে A[k][j] <= A[k][i] হয়।
- উত্তর = মোট কলাম - সর্বোচ্চ LIS দৈর্ঘ্য।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minDeletionSize(vector<string>& A) {
int ret = 0, n = A.size(), 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]);
}
}
}
return ret == 0 ? m - 1 : m - ret;
}
};
int main() {
Solution ob;
vector<string> v = {"cbcdb","ccbxc"};
cout << ob.minDeletionSize(v);
return 0;
}ইনপুট ও আউটপুট
ইনপুট: {"cbcdb","ccbxc"}
আউটপুট: 3
