Welcome to Subscribe On Youtube

• Java
• C++
• Python
• Go

• import java.util.*;
  
  /**
  
   Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.
  
   Return the maximum possible length of s.
  
  
  
   Example 1:
  
   Input: arr = ["un","iq","ue"]
   Output: 4
   Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
   Maximum length is 4.
  
   Example 2:
  
   Input: arr = ["cha","r","act","ers"]
   Output: 6
   Explanation: Possible solutions are "chaers" and "acters".
  
   Example 3:
  
   Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
   Output: 26
  
  
   Constraints:
  
   1 <= arr.length <= 16
   1 <= arr[i].length <= 26
   arr[i] contains only lower case English letters.
  
   */
  public class Maximum_Length_of_a_Concatenated_String_with_Unique_Characters {
  
      public static void main(String[] args) {
          Maximum_Length_of_a_Concatenated_String_with_Unique_Characters out = new Maximum_Length_of_a_Concatenated_String_with_Unique_Characters();
          Solution s = out.new Solution();
  
          ArrayList<String> input = new ArrayList<>();
  //        input.add("cha");
  //        input.add("r");
  //        input.add("act");
  //        input.add("ers");
  
          input.add("un");
          input.add("iq");
          input.add("ue"); // output: 4
  
  //        input.add("yy");
  //        input.add("bkhwmpbiisbldzknpm");
  
          System.out.println(s.maxLength(input));
      }
  
      class Solution {
  
          int result = 0;
  
          public int maxLength(List<String> array) {
  
              Set<Integer> visitedIndex = new HashSet<>();
  
              dfs("", 0, array, visitedIndex);
  
              return result;
          }
  
          private void dfs(String s, int startIndex, List<String> array, Set<Integer> visitedIndex) {
  
              System.out.println(s);
  //            System.out.println(startIndex + "\n");
  
              if (isUniquestring(s)) {
                  result = Math.max(result, s.length());
              } else {
                  return;
              }
  
              for (int i = startIndex; i < array.size(); i++) {
  
                  if (!visitedIndex.contains(i) && isUniqueChar(s, array.get(i))) {
  
                      visitedIndex.add(i);
  
                      dfs(s + array.get(i), i+1, array, visitedIndex);
  
                      visitedIndex.remove(i);
                  }
              }
          }
  
          private boolean isUniqueChar(String s1, String s2) {
              for (char each: s1.toCharArray()) {
                  if (s2.indexOf(each) >= 0) {
                      return false;
                  }
              }
  
              return true;
          }
  
          private boolean isUniquestring(String s) {
              int[] charCount = new int[256];
  
              for (char each: s.toCharArray()) {
                  charCount[each]++;
  
                  if (charCount[each] > 1) {
                      return false;
                  }
              }
              return true;
          }
      }
  
  }
  
  
  ############
  
  class Solution {
      public int maxLength(List<String> arr) {
          int ans = 0;
          List<Integer> masks = new ArrayList<>();
          masks.add(0);
          for (var s : arr) {
              int mask = 0;
              for (int i = 0; i < s.length(); ++i) {
                  int j = s.charAt(i) - 'a';
                  if (((mask >> j) & 1) == 1) {
                      mask = 0;
                      break;
                  }
                  mask |= 1 << j;
              }
              if (mask == 0) {
                  continue;
              }
              int n = masks.size();
              for (int i = 0; i < n; ++i) {
                  int m = masks.get(i);
                  if ((m & mask) == 0) {
                      masks.add(m | mask);
                      ans = Math.max(ans, Integer.bitCount(m | mask));
                  }
              }
          }
          return ans;
      }
  }
  

• // OJ: https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/
  // Time: O(2^N)
  // Space: O(N)
  class Solution {
  public:
      int maxLength(vector<string>& A) {
          vector<int> v;
          for (auto &s : A) {
              int bs = 0, i = 0;
              for (; i < s.size(); ++i) {
                  int j = s[i] - 'a';
                  if (bs >> j & 1) break;
                  bs |= 1 << j;
              }
              if (i == s.size()) v.push_back(bs);
          }
          int ans = 0;
          for (int m = 1; m < 1 << v.size(); ++m) {
              int bs = 0, i = 0;
              for (; i < v.size(); ++i) {
                  if ((m >> i & 1) == 0) continue;
                  if (bs & v[i]) break;
                  bs |= v[i];
              }
              ans = max(ans, __builtin_popcount(bs));
          }
          return ans;
      }
  };
  

• class Solution:
      def maxLength(self, arr: List[str]) -> int:
          ans = 0
          masks = [0]
          for s in arr:
              mask = 0
              for c in s:
                  i = ord(c) - ord('a')
                  if mask >> i & 1:
                      mask = 0
                      break
                  mask |= 1 << i
              if mask == 0:
                  continue
              for m in masks:
                  if m & mask == 0:
                      masks.append(m | mask)
                      ans = max(ans, (m | mask).bit_count())
          return ans
  
  ############
  
  # 1239. Maximum Length of a Concatenated String with Unique Characters
  # https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/
  
  class Solution:
      def maxLength(self, A: List[str]):
          dp = [set()]
          
          for a in A:
              if len(set(a)) < len(a): continue
              
              a = set(a)
              for b in dp[:]:
                  if a & b: continue
                  dp.append(a | b)
              
              
          return max(len(a) for a in dp)
  
      def maxLength(self, arr: List[str]):
          n = len(arr)
          res = 0
          
          for i in range(1 << n):
              tmp = ""
              for j in range(n):
                  if i >> j & 1:
                      tmp += arr[j]
              
              c = Counter(tmp)
              if all(v == 1 for v in c.values()):
                  res = max(res, len(tmp))
              
          return res
  

• func maxLength(arr []string) (ans int) {
  	masks := []int{0}
  	for _, s := range arr {
  		mask := 0
  		for _, c := range s {
  			i := int(c - 'a')
  			if mask>>i&1 == 1 {
  				mask = 0
  				break
  			}
  			mask |= 1 << i
  		}
  		if mask == 0 {
  			continue
  		}
  		n := len(masks)
  		for _, m := range masks[:n] {
  			if m&mask == 0 {
  				masks = append(masks, m|mask)
  				ans = max(ans, bits.OnesCount(uint(m|mask)))
  			}
  		}
  	}
  	return
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

All Problems

All Solutions