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):
    #
    # Write your code here.
    #
    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()

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()));
    }
}

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;
}

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("%dn", maxScore());
    
    return 0;
}