I am solving this problem:

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:
Input: arr = ["cha", "r", "ab", "bc", "m"]
Output: 5
Explanation: Solution is "charm"
```

I am using the below backtracking approach:

```
int max = 0;
public int maxLength(List<String> arr) {
getMaxLength("", 0, arr);
return max;
}
private void getMaxLength(String str, int idx, List<String> arr) {
if(idx == arr.size()) {
max = Math.max(max, str.length());
return;
}
for(int i = idx; i < arr.size(); i++) {
String curr = str + arr.get(i);
if(isUnique(curr)) {
max = Math.max(max, curr.length());
getMaxLength(curr, i + 1, arr);
}
}
}
private boolean isUnique(String s) {
int[] count = new int[26];
for(char ch : s.toCharArray()) {
count[ch - 'a']++;
}
for(int n : count) {
if(n > 1) return false;
}
return true;
}
```

As we can see below there are a lot of recomputations like branch #2 & 4 (r => ab => m):

```
["cha", "r", "ab", "bc", "m"]
1. cha => r => ab => bc [invalid branch: backtrack]
2. cha => r => ab => m
3. r => ab => bc [invalid branch: backtrack]
4. r => ab => m
5. ab => bc [invalid branch: backtrack]
6. ab => m
```

Is there any way here to cache/memoize the results?

Read more here: https://stackoverflow.com/questions/66270711/how-to-use-dynamic-programming-for-this-question

### Content Attribution

This content was originally published by qrius at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.