Độ dài tối đa của một chuỗi liên kết với các ký tự duy nhất trong C ++

Giả sử chúng ta có một mảng chuỗi arr. Chuỗi s là một chuỗi nối con của chuỗi arr có các ký tự duy nhất. Tìm độ dài lớn nhất có thể có của s. Nếu đầu vào là [“cha”, “r”, “act”, “ers”], thì đầu ra sẽ là 6, các giải pháp khả thi là “chaers” và “acters”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một phương thức được gọi là ok () và điều này sẽ nhận các chuỗi s và t. Điều này sẽ hoạt động như dưới đây
• tạo một bản đồ x
• cho tôi trong phạm vi từ 0 đến kích thước của s
  • tăng x [s [i]] lên 1
  • nếu x [s [i]]> 1, thì trả về false
• cho tôi trong phạm vi từ 0 đến kích thước của t
  • tăng x [t [i]] lên 1
  • nếu x [t [i]]> 1, thì trả về false
• trả về true
• phương pháp thực tế sẽ giống như bên dưới -
• tạo một mảng các chuỗi được gọi là v và ans:=0, chèn một chuỗi trống vào v
• cho tôi trong phạm vi từ 0 đến kích thước của arr
  • n:=kích thước của v
  • cho j trong phạm vi từ 0 đến n - 1
    • nếu ok (v [j], arr [i]) là đúng, thì
      • t:=v [j] + arr [i]
      • chèn t vào v
      • ans:=max của ans và kích thước của t
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

6