Question: Juniper Networks IITK
1
Entering edit mode
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 &gt; 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 &gt;= k - 1
ans[i] = 1

if i &gt; 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)
``````
1
Entering edit mode

SORT IT WISELY

``````for (i = 1; i &lt; n; i++){
for (j = 0; j &lt; n - i; j++) {
if (a[j].score&lt;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&gt;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&gt;0){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}

}
}
}
``````