In this post, we will solve 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 A, & A, are the smallest and the largest positions (from the initial word) respectively in A; and B, & B, are the smallest and the largest positions (from the initial word) respectively in B. then the following statements hold true:
A; Aj.
B₁ ≤ Bj, &
Aj < Bi
I.e., the positions of the subsequences should not cross over each other.
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?
Input Format
Input contains a word S composed of lowercase English letters in a single line.
Output Format
Output the maximum score the boys can get from S.
Sample Input
eeegeeksforskeeggeeks
Sample Output
50
Explanation
A possible optimal solution is eee-g-ee-ksfor-skeeggeeks being eeeee the one subsequence and skeeggeeks the other one. We can also select eegee in place of eeeee, as both have the same length.

Play with words C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct node{
int i;
int j;
int val;
};
int r[3003][3003];
struct node az[3003][3003];
int max(int i, int j){
return i>j?i:j;
}
int dp(char *a,int s, int e){
int m,n;
if(r[s][e]!=-1){
//printf("1\n");
return r[s][e];
}
if(s==e){
//printf("2\n");
r[s][e]= 1;
}
else if(e-s==1){
if(a[s]==a[e]){
r[s][e]= 2;
}
else
r[s][e]= max(dp(a,s+1,e),dp(a,s,e-1));
}
else if(a[s]==a[e]){
r[s][e]= 2+dp(a,s+1,e-1);
}
else{
r[s][e]= max(dp(a,s+1,e),dp(a,s,e-1));
}
return r[s][e];
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int i,j,n,ii,jj,n1,it,jt;
char a[3003],b[3003];
scanf("%s",a);
i=0;
while(a[i++]!='\0');
n=i-1;
for(i=0;i<=n+1;i++){
for(j=0;j<=n+1;j++){
r[i][j]=-1;
}
}
n1=0;
for(i=0;i<n-1;i++){
it=dp(a,0,i)*dp(a,i+1,n-1);
if(n1<it)
n1=it;
}
printf("%d",n1);
return 0;
}
Play with words C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
using LL = long long;
std::unordered_map<LL,LL> cache;
LL get_biggest_pal(std::string const& s, LL i, LL j) {
if (j < i || i >= s.size() || j < 0)
return 0;
LL key = i << 32 | j;
auto r = cache.find(key);
if (r != cache.end())
return r->second;
if (s[i] == s[j]) {
cache[key] = (1 + (i!=j)) + get_biggest_pal(s, i+1, j-1);
}
else {
cache[key] = std::max(
get_biggest_pal(s, i+1,j),
get_biggest_pal(s, i,j-1)
);
}
return cache[key];
}
int main() {
std::string s;
std::cin >> s;
int maxx = 0;
for (int i = 0; i < s.size(); ++i) {
if (maxx >= i * (s.size() - i - 1))
continue;
int maxr = get_biggest_pal(s, 0, i);
int maxl = get_biggest_pal(s, i+1, s.size() -1);
if (maxr*maxl > maxx)
maxx = maxr * maxl;
}
std::cout << maxx << std::endl;
return 0;
}
Play with words C Sharp Solution
using System;
namespace PlayWithWords
{
class Solution
{
// Matrix multiplication modified
public static void Main(string[] args)
{
var s = Console.ReadLine();
var n = s.Length;
var table = new int[n, n];
for (var i = 0; i < n; i++)
{
table[i, i] = 1;
}
for (var i = 2; i <= n; i++)
{
for (var j = 0; j < n - i + 1; j++)
{
var k = j + i - 1;
if (s[j] == s[k] && i == 2)
{
table[j, k] = 2;
}
else if (s[j] == s[k])
{
table[j, k] = table[j + 1, k - 1] + 2;
}
else
{
table[j, k] = Math.Max(table[j, k - 1], table[j + 1, k]);
}
}
}
var ans = 1L;
for (var i = 1; i < n - 1; i++)
{
int mul = table[0, i] * table[i + 1, n - 1];
ans = Math.Max(ans, mul);
}
Console.WriteLine(ans);
}
}
}
Play with words Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
import java.util.Arrays;
class Result {
/*
* Complete the 'playWithWords' function below.
*
* The function is expected to return an INTEGER.
* The function accepts STRING s as parameter.
*/
public static int playWithWords(String s) {
// Write your code here
int length = s.length();
int[][] dp = new int[length][length];
for (int i = length - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i+1; j < length; j++) {
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 < length; i++)
{
System.out.println(Arrays.toString(dp[i]));
}*/
int maxProduct = 0;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length - 1; j++) {
maxProduct = Math.max(maxProduct, dp[i][j] * dp[j + 1][length - 1]);
}
}
return maxProduct;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String s = bufferedReader.readLine();
int result = Result.playWithWords(s);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
Play with words JavaScript Solution
'use strict';
"eeaba"
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'playWithWords' function below.
*
* The function is expected to return an INTEGER.
* The function accepts STRING s as parameter.
*/
function playWithWords(input) {
// Write your code here
let mt = new Array(input.length);
for (let i = 0; i < mt.length; i += 1) {
mt[i] = new Array(input.length);
mt[i][i] = 1;
}
for (let sublen = 2; sublen <= input.length; sublen += 1) {
for (let i = 0; i <= input.length - sublen; i += 1) {
let j = i + sublen - 1;
if (input[i] === input[j] && sublen === 2) {
mt[i][j] = 2;
} else if (input[i] === input[j]) {
mt[i][j] = mt[i + 1][j - 1] + 2;
} else {
mt[i][j] = Math.max(mt[i + 1][j], mt[i][j - 1]);
}
}
}
let max = 0;
for (let i = 0; i < input.length - 1; i += 1) {
max = Math.max(max, mt[0][i] * mt[i + 1][input.length - 1]);
}
return max;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const s = readLine();
const result = playWithWords(s);
ws.write(result + '\n');
ws.end();
}
Play with words Python Solution
str1=input()
n=len(str1)
table=[[0 for i in range(n)] for j in range(n)]
for i in range(n):
table[i][i]=1
for sl in range(2,n+1):
for i in range(n-sl+1):
j=i+sl-1
if str1[i]==str1[j] and sl==2:
table[i][j]=2
elif str1[i]==str1[j]:
table[i][j]=table[i+1][j-1]+2
else:
table[i][j]=max(table[i][j-1],table[i+1][j])
lis1=[]
for i in range(n):
if i+1<n:
lis1.append(table[0][i]*table[i+1][n-1])
print(max(lis1))