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