C++에서 고유한 문자가 있는 연결된 문자열의 최대 길이

arr 문자열 배열이 있다고 가정합니다. 문자열 s는 고유한 문자를 가진 arr의 하위 시퀀스를 연결한 것입니다. s의 가능한 최대 길이를 찾으십시오. 입력이 ["cha", "r", "act", "ers"]와 같은 경우 출력은 6이고 가능한 솔루션은 "chaers" 및 "acters"입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ok()라는 메서드를 하나 만들고 문자열 s와 t를 사용합니다. 다음과 같이 작동합니다.
• 하나의 지도 만들기 x
• 0부터 s
  까지의 범위에 있는 i의 경우
  • x[s[i]] 1씩 증가
  • x[s[i]]> 1이면 false를 반환합니다.
• 0에서 t
  까지의 범위에 있는 i의 경우
  • x[t[i]] 1씩 증가
  • x[t[i]]> 1이면 false를 반환합니다.
• 참을 반환
• 실제 방법은 아래와 같습니다 -
• v라는 문자열의 배열을 만들고 ans :=0, 하나의 빈 문자열을 v에 삽입
• 0에서 arr 크기까지의 범위에 있는 i의 경우
  • n :=v의 크기
  • 0 ~ n – 1 범위의 j에 대해
    • ok(v[j], arr[i])가 참이면
      • t :=v[j] + arr[i]
      • v에 t 삽입
      • ans :=as의 최대값과 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