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?

hackerrank play with words problem solution


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

{"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}