ความยาวสูงสุดของสตริงที่ต่อกันด้วยอักขระที่ไม่ซ้ำใน C++

สมมติว่าเรามีอาร์เรย์ของสตริง arr สตริง s เป็นการต่อกันของลำดับย่อยของ arr ซึ่งมีอักขระเฉพาะ จงหาความยาวสูงสุดของ s หากอินพุตเป็น ["cha", "r", "act", "ers"] ผลลัพธ์จะเป็น 6 วิธีแก้ปัญหาที่เป็นไปได้คือ "chaers" และ "acters"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างเมธอดหนึ่งวิธีที่เรียกว่า ok() ซึ่งจะใช้สตริง s และ t ซึ่งจะทำหน้าที่ดังต่อไปนี้
• สร้างหนึ่งแผนที่ x
• สำหรับ i ในช่วง 0 ถึงขนาด s
  • เพิ่ม x[s[i]] ขึ้น 1
  • ถ้า x[s[i]]> 1 ให้คืนค่าเท็จ
• สำหรับ i ในช่วง 0 ถึงขนาดของ t
  • เพิ่ม x[t[i]] ขึ้น 1
  • ถ้า x[t[i]]> 1 ให้คืนค่าเท็จ
• คืนค่าจริง
• วิธีการจริงจะมีลักษณะดังนี้ −
• สร้างอาร์เรย์ของสตริงที่เรียกว่า v และ ans :=0 ใส่สตริงว่างลงใน v
• สำหรับ i ในช่วง 0 ถึงขนาดของ arr
  • n :=ขนาดของวี
  • สำหรับ j ในช่วง 0 ถึง n – 1
    • ถ้า ok(v[j], arr[i]) เป็นจริง แล้ว
      • t :=v[j] + arr[i]
      • ใส่ t ลงใน v
      • ans :=สูงสุดของ ans และขนาดของ 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"]

ผลลัพธ์

6