Question: Juniper Networks IITK
1
Entering edit mode
ADD COMMENTlink 15 days ago QWERTY474 • 40 • updated 15 days ago Gurankit Pal Singh 110
1
Entering edit mode

Solution for Question 1

We can use dynamic programming to approach this problem. First, let dp[x][y] represent if the substring from index x to y is a palindrome or not.

We can define the transitions as follows: dp[j][j + i - 1] = 1 if s[j] == s[j + i - 1] and dp[j + 1][j + i - 2], here we are iterating on the length of a substring i starting at the index j.

Once, we have this dp calculated, we can define ans[i] as the maximum number of palindromic substrings of length at least k that can be selected from string up to the index i. We can define the transitions as follows: ans[i] = max(ans[i - 1], ans[j] + 1) if dp[j + 1][i] = 1 where j = 0 to i - k, i.e. we can either select some substring from j + 1 to i, if this is a palindrome and add it to the max answer obtained before j.

Finally, the maximum value of ans array can be reported as our answer.

Pseudo Code:

solve(str, k)
    n = len(str)
    dp = [[0] * n for i in range(n)]

    for i in range(1, n + 1)
        for j in range(n)
            if j + i > n
                break
            if i == 1 or (i == 2 and str[j] == str[j + i - 1]) or (dp[j + 1][j + i - 2] == 1 and str[j] == str[j + i - 1])
                dp[j][j + i - 1] = 1

    ans = [0 for i in range(n)]
    for i in range(n):
        if dp[0][i] == 1 and i >= k - 1
            ans[i] = 1

        if i > 0
            ans[i] = max(ans[i], ans[i - 1])

        for j in range(i-k+1)
            if dp[j + 1][i] == 1
                ans[i] = max(ans[i], ans[j] + 1)

    return max(ans)
ADD COMMENTlink 15 days ago Gurankit Pal Singh 110
1
Entering edit mode

SORT IT WISELY

for (i = 1; i < n; i++){
    for (j = 0; j < n - i; j++) {
      if (a[j].score<a[j + 1].score) {
        temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
      }

      else if(a[j].score==a[j + 1].score){
          result = strcmp(a[j].first_name, a[j+1].first_name);
          if(result>0){
               temp = a[j];
             a[j] = a[j + 1];
             a[j + 1] = temp;
          }

          else if(result==0){
               result = strcmp(a[j].last_name, a[j+1].last_name);
               if(result>0){
                   temp = a[j];
                 a[j] = a[j + 1];
                 a[j + 1] = temp;
              }
          }

     }
    }
}
ADD COMMENTlink 15 days ago QWERTY474 • 40
0
Entering edit mode

enter image description here

ADD COMMENTlink 15 days ago QWERTY474 • 40

Login before adding your answer.

Similar Posts
Loading Similar Posts