HackerRank Play with words problem solution

In this HackerRank Play with words problem solution Shaka and his brother have created a boring game which is played like this:

They take a word composed of lowercase English letters and try to get the maximum possible score by building exactly 2 palindromic subsequences. The score obtained is the product of the length of these 2 subsequences.

Let's say A and B are two subsequences from the initial string. If Ai & Aj are the smallest and the largest positions (from the initial word) respectively in A; and Bi & Bj are the smallest and the largest positions (from the initial word) respectively in B, then the following statements hold true:

• Ai <= Aj,
• Bi <= Bj, &
• Aj < Bi.

Hence the score obtained is the product of lengths of subsequences A & B. Such subsequences can be numerous for a larger initial word, and hence it becomes harder to find out the maximum possible score. Can you help Shaka and his brother find this out?

Problem solution in Python.

```#!/bin/python3

import os
import sys

#
# Complete the playWithWords function below.
#
def playWithWords(s):
#
#
arr = s
n = len(arr)
# Create a table to store results of subproblems
L = [[0] * n for _ in range(n)]

# Strings of length 1 are palindrome of length 1
for i in range(n):
L[i][i] = 1

for cl in range(2, n+1):
for i in range(n-cl+1):
j = i+cl-1
if arr[i] == arr[j] and cl == 2:
L[i][j] = 2
elif arr[i] == arr[j]:
L[i][j] = L[i+1][j-1] + 2
else:
L[i][j] = max(L[i][j-1], L[i+1][j])

res=1
for i in range(n-1):
res = max(res, L[0][i]*L[i+1][n-1])

return res

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

s = input()

result = playWithWords(s)

fptr.write(str(result) + '\n')

fptr.close()
```

{"mode":"full","isActive":false}

Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

public static int getMaxPalindromicSubsequenceProd(String s) {
if(s==null || s.length()<2) return 0;

int[][] dp=new int[s.length()][s.length()];
for(int l=1;l<=s.length();l++) {
for(int i=0;i<s.length()-l+1;i++) {
int j=i+l-1;
if(l==1) {
dp[i][j]=1;
} else if(l==2 && s.charAt(i)==s.charAt(j)) {
dp[i][j]=2;
} else {
if(s.charAt(i)==s.charAt(j)) dp[i][j]=dp[i+1][j-1]+2;
else dp[i][j]=Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}

//for(int i=0;i<dp.length;i++) System.out.println(Arrays.toString(dp[i]));

int max=Integer.MIN_VALUE;
for(int k=0;k<s.length()-1;k++) {
//System.out.println(k + "  " + dp[0][k] + "  " + dp[k+1][s.length()-1]);
max=Math.max(max, dp[0][k]*dp[k+1][s.length()-1]);
}

return max;
}

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in=new Scanner(System.in);
System.out.println(getMaxPalindromicSubsequenceProd(in.next()));
}
}```

{"mode":"full","isActive":false}

Problem solution in C++.

```#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <stdlib.h>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <numeric>
#include <utility>
#include <deque>
#include <stack>
#include <bitset>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <queue>
#include <limits>
#include <fstream>
#include <list>
#include <sstream>
#include <iostream>
#include <iomanip>

using namespace std;
#define MAX 3005
string s;
int n;
int dp[ MAX ][ MAX ];
int solve( int ini , int end ){

if( ini > end || ini >=n || end <0 )
return 0;

if( dp[ ini ][ end ] != -1 )
return dp[ ini ][ end ];

int res = 0;

if( s[ini] == s[end] ){
int incr = 2;
if( ini == end )
incr = 1;

res = max( res , incr + solve( ini + 1 , end - 1 ) );

}else{
res = max( res , solve( ini , end - 1 ));
res = max( res , solve( ini + 1 , end ) );

res = max( res , solve( ini + 1 , end - 1 ));
}
return dp[ ini ][ end ] = res;
}

int main(){
cin>>s;
n = s.size();
int ans = 0;
memset( dp , -1 , sizeof( dp ) );

for( int i = 0 ; i < n ; ++i ){
ans = max( ans , solve( 0 , i ) * solve( i + 1 , n - 1 ) );

}
cout<<ans<<endl;
return 0;
}
```

{"mode":"full","isActive":false}

Problem solution in C.

```#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SIZE 3001
#define MOD 1000000007

typedef long long LL;

int N;
char str[SIZE];
int a[SIZE][SIZE], b[SIZE][SIZE];

int max(int a, int b)
{
if(a > b)
return a;
return b;
}

int maxScore()
{
int i, j;
int res = 0;

memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));

for(i = 1; i <= N; i++)
{
for(j = 0; j < N-i+1; j++)
{
if(i == 1)
a[j][j+i-1] = 1;
else if(i == 2)
{
if(str[j] == str[j+i-1])
a[j][j+i-1] = 2;
else
a[j][j+i-1] = 1;
}
else
{
if(str[j] == str[j+i-1])
a[j][j+i-1] = a[j+1][j+i-2] + 2;
else
a[j][j+i-1] = max(a[j][j+i-2], a[j+1][j+i-1]);
}
}
}

for(i = 1; i <= N; i++)
{
for(j = N-1; j >= i-1; j--)
{
if(i == 1)
b[j-i+1][j] = 1;
else if(i == 2)
{
if(str[j-i+1] == str[j])
b[j-i+1][j] = 2;
else
b[j-i+1][j] = 1;
}
else
{
if(str[j-i+1] == str[j])
b[j-i+1][j] = b[j-i+2][j-1] + 2;
else
b[j-i+1][j] = max(b[j-i+1][j-1], b[j-i+2][j]);
}
}
}

for(i = 0; i < N-1; i++)
res = max(res, a[0][i]*b[i+1][N-1]);

return res;
}

int main(int argc, char *argv[])
{
scanf("%s", str);
N = strlen(str);
printf("%d\n", maxScore());

return 0;
}

```

{"mode":"full","isActive":false}