C++-এ অনন্য অক্ষর সহ একটি সংযুক্ত স্ট্রিং-এর সর্বাধিক দৈর্ঘ্য

ধরুন আমরা একটি স্ট্রিং arr আছে. স্ট্রিং s হল arr-এর একটি সাব-সিকোয়েন্সের সংমিশ্রণ যার অনন্য অক্ষর রয়েছে। s এর সর্বাধিক সম্ভাব্য দৈর্ঘ্য খুঁজুন। যদি ইনপুট হয় [“cha”, “r”, “act”, “ers”], তাহলে আউটপুট হবে 6, সম্ভাব্য সমাধান হল “chaers” এবং “acters”।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

ok() নামে একটি পদ্ধতি তৈরি করুন এবং এতে স্ট্রিং s এবং t লাগবে। এটি নিচের মত কাজ করবে
একটি মানচিত্র তৈরি করুন x
আমি 0 থেকে s
- x[s[i]] 1 দ্বারা বাড়ান
- যদি x[s[i]]> 1 হয়, তাহলে মিথ্যা ফেরত দিন
আমি 0 থেকে t
- x[t[i]] 1 দ্বারা বাড়ান
- যদি x[t[i]]> 1 হয়, তাহলে মিথ্যা ফেরত দিন
সত্য ফেরত দিন
প্রকৃত পদ্ধতি নিচের মত হবে -
v নামক স্ট্রিংগুলির একটি অ্যারে তৈরি করুন এবং উত্তর :=0, একটি খালি স্ট্রিং v এ প্রবেশ করান
আমি 0 থেকে arr
- n :=v এর আকার
- 0 থেকে n – 1
  - যদি ok(v[j], arr[i]) সত্য হয়, তাহলে
    - t :=v[j] + arr[i]
    - v-এ t ঢোকান
    - উত্তর :=উত্তরের সর্বোচ্চ এবং t এর আকার
উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool ok(string s, string t){
      map <char, int > x;
      for(int i = 0; i < s.size(); i++){
         x[s[i]]++;
         if(x[s[i]] >1)return false;
      }
      for(int i = 0; i < t.size(); i++){
         x[t[i]]++;
         if(x[t[i]]>1)return false;
      }
      return true;
   }
   int maxLength(vector<string>& arr) {
      vector <string> v;
      int ans = 0;
      v.push_back("");
      for(int i = 0; i < arr.size(); i++){
         int n = v.size();
         for(int j = 0; j < n; j++){
            if(ok(v[j],arr[i])){
               string t = v[j]+arr[i];
               v.push_back(t);
               ans = max(ans,(int)t.size());
            }
         }
      }
      return ans;
   }
};
main(){
   vector<string> v = {"cha","r","act","ers"};
   Solution ob;
   cout << (ob.maxLength(v));
}

ইনপুট

["cha","r","act","ers"]