Create 1239.Maximum-Length-of-a-Concatenated-String-with-Unique-Characters.cpp

wisdompeak · web-flow · commit 3704824be855 · 2021-06-18T22:24:09.000-07:00
diff --git a/Bit_Manipulation/1239.Maximum-Length-of-a-Concatenated-String-with-Unique-Characters/1239.Maximum-Length-of-a-Concatenated-String-with-Unique-Characters.cpp b/Bit_Manipulation/1239.Maximum-Length-of-a-Concatenated-String-with-Unique-Characters/1239.Maximum-Length-of-a-Concatenated-String-with-Unique-Characters.cpp
@@ -0,0 +1,42 @@
+typedef long long ll;
+class Solution {
+    int ret = 0;
+public:
+    int maxLength(vector<string>& arr) 
+    {        
+        vector<ll>codes;
+        for (int i=0; i<arr.size(); i++)
+        {
+            ll code = 0;
+            int flag = 1;
+            for (auto ch: arr[i])
+            {
+                if ((code>>(ch-'a'))&1)
+                {
+                    flag = 0;
+                    break;
+                }
+                code += (1<<(ch-'a'));
+            }
+            if (flag)
+                codes.push_back(code);
+        }
+
+        ll bits = 0;
+        for (int i=0; i<codes.size(); i++)
+            dfs(codes, i, codes[i]);
+        return ret;
+    }
+
+    void dfs(vector<ll>codes, int i, ll bits)
+    {
+        ret = max(ret, __builtin_popcount(bits));
+        for (int j=i+1; j<codes.size(); j++)
+        {
+            if ((bits & codes[j])==0)
+            {
+                dfs(codes, j, bits + codes[j]);
+            }            
+        }
+    }
+};
