Maximum Length of a Concatenated String with Unique Characters - Leetcode 1239 - Python

0:00 - Read the problem
1:40 - Drawing Explanation
5:50 - Coding Explanation

leetcode 1239
#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[tanson]

Wow... You made this problem so simple... Below is the java implementation of the same

class Solution {
public int maxLength(List<String> arr) {
if(arr.size()==1){
if(checkValidity(new HashSet<>(), arr.get(0)))
return arr.get(0).length();
else return 0;
}

return maxLength(arr, 0, new HashSet<>());
}

public int maxLength(List<String> arr, int index, Set<Character> set) {
if(index==arr.size())
return set.size();

int incIdx = 0;
if(checkValidity(set, arr.get(index))) {
incIdx = maxLength(arr, index + 1, set);
String s = arr.get(index);
for (int i = 0; i < s.length(); i++)
set.remove(s.charAt(i));
}
return Math.max(incIdx, maxLength(arr, index+1, set));
}

private boolean checkValidity(Set<Character> set, String s) {
for(int i=0;i<s.length();i++){

for(int j=0;j<i;j++)
set.remove(s.charAt(j));
return false;
}else{
set.add(s.charAt(i));
}
}
return true;
}
}

[priyansh.saxena]

Here is a simplified version of this solution.

class Solution:
def maxLength(self, arr: List[str]) -> int:
N = len(arr)
dp = {}
def backtrack(i, cur):
if (i, cur) in dp:
return dp[(i, cur)]
if i>=N:
return len(cur)
else:
if not and len(set(arr[i])) == len(arr[i]):
dp[(i, cur)] = max(backtrack(i+1, cur+arr[i]), backtrack(i+1, cur) )
return dp[(i, cur)]
else:
dp[(i, cur)] = backtrack(i+1, cur)
return dp[(i, cur)]
return backtrack(0, "")

All thanks to @neetocde for making me able to write this.

[SANJAYSINGH-jthf]

My Java Solution: Main trick is to not add in original Hashset in helper function.

class Solution {
public int maxLength(List<String> arr) {
HashSet<Character> set= new HashSet<>();
return backtrack(arr, 0, set);
}
public int backtrack(List<String> arr, int i, HashSet<Character> set){
if(i==arr.size()) return set.size();
int res=0;
if(!overlap(arr.get(i), set)){
for(int

}
res = backtrack(arr, i+1, set) ;
for(int

}
}
return Math.max(res, backtrack(arr, i+1, set) );
}
public boolean overlap(String str, HashSet<Character> set){
HashSet<Character> prev = new HashSet<>();
for(int k=0;k<str.length();k++){
char c = str.charAt(k);
true;}
prev.add(c);
}
return false;//not in set already
}
}

[brecoldyls]

Very nice use of backtracking! I actually concatenated the strings in my solution, but I think using the set like you did would be faster. Also I like the use of counter; I don’t use that one enough 😅 I always feel clever when I use a data structure from the standard library that’s not a built-in

[chenzhuo]

Hi Neet, thanks for doing the video. Can you please do 843 Guess the Word which is the most popular question at Google for the past 6 month! thank you

[terryyang]

Thank you so much for this video, but I'm having a hard time understanding "Counter" here in line 6. says "name Counter is not defined" in my case

[abhishekmore]

@NeetCode What is the time complexity for this solution

[luciaveldera]

Can anyone explain it to me why we have to clean up after we backtracked and store a new concatenation in "res" variable?

[lohe]

thanks your decision tree is so powerful, I using that concept to my c++ code and let me easy to understand how backtracking run thanks for your help!

[edwardteach]

U a God. Python simpler implementation with DFS/backtracking:

class Solution(object):
def maxLength(self, arr):
"""
:type arr: List[str]
:rtype: int
"""
self.ans = 0

def hasDuplicates(s):
return len(s) > len(set(s))


def backtrack(idx, s):
self.ans = max(self.ans, len(s))

if idx >= len(arr):
return

for i in range(idx, len(arr)):
if not hasDuplicates(s + arr[i]):
backtrack(i + 1, s + arr[i])

if not arr:
return 0
backtrack(0, "")
return self.ans

[ayoubalem]

Hmmm thiw was my solution :

class Solution:
def maxLength(self, arr: List[str]) -> int:
count = 0
Max = 0
duplicates = self.check(arr)
res = [0]

def backtrack(seen, i):
if i >= len(arr):
res[0] = max(res[0], len(seen))
return

if not (set(arr[i]) & seen) and (i not in duplicates):
temp = seen.union(set(arr[i]))
backtrack(temp, i + 1)

backtrack(seen, i + 1)

backtrack(set(), 0)

return res[0]



this function will return a set of indexes of the word that contain duplicates


def check(self, arr):
res = set()
for i, word in enumerate(arr):
seen = set()
for c in word:
if c in seen:
res.add(i)
break
seen.add(c)

return res

[thomaswinn]

Can someone explain to me line 23 - line 26? I have a hard time understanding why this is needed.

[Lucan_]

Two Loops + Set did the trick for me. Btw noice soln😃

[israaezzat]

what is the time and space complexity of such solution ?

[rabbyhossain]

More cleaner I guess

class Solution:

def maxLength(self, arr: List[str]) -> int:
self.maxLen = 0

def backtrack(i: int, sub: str):
if i >= len(arr): return

tmp = sub
sub += arr[i]
charSet = set(sub)
if len(sub) == len(charSet):
self.maxLen = max(self.maxLen, len(sub))

backtrack(i+1, sub)
backtrack(i+1, tmp)

backtrack(0, '')

return self.maxLen

[OMFGallusernamesgone]

can't you just use kadane's algorithm?