HackerRank Play with words Problem Solution

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

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.

Table of Contents

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