educative.io

For the DP solution, Why startIndex start from the last character of the string

Courses
,
#1

The code below, as it starts from last character of the string, the endIndex will be beyond the string, as a result, the first iteration in case of startIndex = st.length() - 1 will never been executed.
for (int startIndex = st.length() - 1; startIndex >= 0; startIndex–) {
for (int endIndex = startIndex + 1; endIndex < st.length(); endIndex++) {

I am wondering maybe start from st.length() -2 could make more sense? any suggestion? Thanks.
for (int startIndex = st.length() - 2; startIndex >= 0; startIndex–) {
for (int endIndex = startIndex + 1; endIndex < st.length(); endIndex++) {

#2

I don’t know why they did this, as it contradicts the explanation saying they will add from the front of the sequence

Here is how I got it working by adding characters from the front in javascript

    for( let end = 1; end < s.length; end++ )
  {
    for( let start = end - 1; start >= 0; start-- )
    {
      if( s[start] === s[end] )
      {
        dpMap[start][end] = 2 + dpMap[start + 1][end - 1];
      } else
      {
        const front = dpMap[start + 1][end];
        const back = dpMap[start][end - 1];
        dpMap[start][end] = Math.max( front, back );
      }
    }
  }
1 Like
#3

Both approaches work i.e., starting from the beginning or the end of the given sequence. We’ll look into this to see if starting from the beginning is more intuitive to the reader and change the published solution based on that.

#4

I too had the same confusion and hence came to the discuss section. I hope they change it soon. It would actually be more intuitive to have the startIndex start from the beginning.

1 Like
#6

Thanks @Philip_Bell
This is both intuitive and comprehensive. :rocket:

#7

The solution and the explanation given is not intuitive enough. Working from the basic solution, I understand the basic premise that is

  1. If the element at the startIndex matches the element at the endIndex , the length of LPS would be two plus the length of LPS till startIndex+1 and endIndex-1 .
  2. If the element at the startIndex does not match the element at the endIndex , we will take the maximum LPS created by either skipping element at the startIndex or the endIndex .

However, what does the table mean - in itself - when I am looking at cddpd on the left and cddpd on the right, and working through the table, what does each index represent ?

Also, why the bottom left half of the table is left unfilled ?

Also as others pointed out, it’s not intuitive to mention “We can start from the beginning of the sequence” and then start the code from the bottom.

Also why for some indices it is OK to pick up previously uncalculated values - like for “cdddd” - [3][4] - the starting position in the given solution - we are picking 2 + [4][3] - and [4][3] has previously been uncalculated.

I am completely confused with this solution/explanation.

1 Like
#8

Thank you. This helps.

#9

https://www.youtube.com/watch?v=_nCsPn7_OgI is a good explanation of the solution