1-String DP Problems


General problem statement for this pattern will vary but most of the time you are given one string with length n and you would need return some result.

Approach:

Most of the problems on this pattern can be solved in in O(n2) complexity. Whenever you are given just 1 string in a DP problem, look for what you get when, for a random substring (str[i...j]) of the given string str, the first and the last characters of the substring happen to match. Can you arrive to some conclusion for that substring if you already know the result for the rest of the substring str[(i + 1)...(j - 1)] ? In most cases, thinking in this direction will give you the DP relationship. So what we will do here is, we will go on computing DP result for all possible substring of all possible lengths (if length of str is n then the possible substring-length can be 1 to n) in the increasing order of the length so that whenever we are computing result for longer length substring, the result for the shorter length substring will be already computed and ready to be used. Notice that for a substring str[i...j], depending on whether str[i] == str[j], you would need the result for str[(i + 1)...(j - 1)]. Length of str[(i + 1)...(j - 1)] is 2 unit less than the length of str[i...j]. So while computing the result for longer substrings you would need the result for the shorter substrings. (Optimal Substructure). Since we are considering the last character of substring, we would see that for some problems we are naturally thinking in terms of suffix, and that is definitely the right way of thinking.

The above mentioned concept will become very clear as we will see several examples being solved using this template in the next few chapters: 


/*
    Bottom-Up Approach: Get the results for the
    shorter length substrings ready (optimal substructure), so that
    when you are computing result for longer length substring (and eventually
    for the whole string) the results for the shorter length substrings
    will already be computed and memoized and ready to be used to compute the
    result for the higher length substrings. So we start from substring_length = 1
    and iterate all the way up to substring_length = n.
 */
n = length(str) 
for (int len = 1; len <= n; ++l) {
   for (int beg = 0; i <= n - len; i++) {
       int end = beg + len - 1;
       if (str[beg] == str[end]) {
           dp[beg][end] = /*your code here*/;
       } else {
           dp[beg][end] = /*your code here*/;
       }
   }
}


Instructor:

Abhishek Dey

Abhishek Dey

Senior SDE | Chief Architect

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.


Help Your Friends save 40% on our products

wave