How to memoize/cache results in this question
Anonymous User
106
Dynamic ProgrammingBacktrackingMemoization

Hello All,

I was recently asked this question in an interview and the interviewer asked to optimize the runtime. This is a classic DFS/backtracking problem, I am just unsure how to use DP here:

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"

My code:

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?

Comments (1)