How to use dynamic programming for this question

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.

%d bloggers like this: