Longest Palindromic Subsequence
Problem Statement :
Steve loves playing with palindromes. He has a string, s, consisting of n lowercase English alphabetic characters (i.e., a through z). He wants to calculate the number of ways to insert exactly 1 lowercase character into string s such that the length of the longest palindromic subsequence of s increases by at least k. Two ways are considered to be different if either of the following conditions are satisfied: The positions of insertion are different. The inserted characters are different. This means there are at most 26*(n+1) different ways to insert exactly 1character into a string of length n. Given q queries consisting of n, k, and s, print the number of different ways of inserting exactly 1 new lowercase letter into string s such that the length of the longest palindromic subsequence of s increases by at least k. Input Format The first line contains a single integer, q, denoting the number of queries. The 2q subsequent lines describe each query over two lines: 1.The first line of a query contains two space-separated integers denoting the respective values of n and k. 2.The second line contains a single string denoting s. Constraints 1 <= q <= 10 1 <= n <= 3000 0 <= k <= 50 It is guaranteed that s consists of lowercase English alphabetic letters (i.e., a to z) only.
Solution :
Solution in C :
In C++ :
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 3005;
int dp[SIZE][SIZE];
int dp2[SIZE][SIZE];
char s[SIZE];
int main(){
CASET{
DRII(n,K);
RS(s+1);
if(K>2)puts("0");
else if(K==0){
printf("%d\n",n*26+26);
}
else{
MS0(dp);
MS0(dp2);
REPP(i,1,n+1)dp2[i][i]=1;
REPP(j,1,n){
for(int k=1;k+j<=n;k++){
int ll=k,rr=k+j;
if(s[ll]==s[rr])dp2[ll][rr]=max(dp2[ll][rr],dp2[ll+1][rr-1]+2);
dp2[ll][rr]=max(dp2[ll][rr],dp2[ll+1][rr]);
dp2[ll][rr]=max(dp2[ll][rr],dp2[ll][rr-1]);
}
}
int ma=0;
for(int i=1;i<n;i++){
for(int j=n;j>i;j--){
if(s[i]==s[j])dp[i][j]=dp[i-1][j+1]+2;
else dp[i][j]=max(dp[i-1][j],dp[i][j+1]);
ma=max(ma,dp[i][j]);
}
}
REPP(i,1,n+1)ma=max(ma,dp[i-1][i+1]+1);
int an=0;
REP(i,n+1){
int me=0;
me=dp[i][i+1]+1;
if(me>=ma+K){
an+=26;
continue;
}
bool used[26]={};
REPP(j,1,n+1){
if(j<=i){
if(dp2[j+1][i]+dp[j-1][i+1]+2>=ma+K)used[s[j]-'a']=1;
}
else{
if(dp2[i+1][j-1]+dp[i][j+1]+2>=ma+K)used[s[j]-'a']=1;
}
}
REP(j,26)
if(used[j]){
an++;
}
}
printf("%d\n",an);
}
}
return 0;
}
In Java :
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static int longestPalindromicSubsequence(String s, int k)
{
int n = s.length();
if (k == 0)
{
return (n + 1) * 26;
}
if (k > 2)
{
return 0;
}
if (n == 1)
{
if (k == 1)
{
return 2;
}
return 0;
}
short pal[][] = computePal(s);
short rightEnds[][] = computeRightEnds(s);
short leftEnds[][] = computeLeftEnds(s);
int sMax = pal[0][n - 1];
boolean ok[][] = new boolean[n + 1][26];
for (int i = 0; i <= n; i++)
{
for (int j = 0; j < n; j++)
{
char c = s.charAt(j);
int min;
int max;
int middle = 0;
if (i <= j)
{
if (i < j)
{
middle = pal[i][j - 1];
}
min = i;
max = j;
}
else
{
if (j + 1 <= i - 1)
{
middle = pal[j + 1][i - 1];
}
min = j;
max = i - 1;
}
int need = sMax + k - middle - 2;
if (need % 2 == 1)
{
need++;
}
if (rightEnds[min][need / 2] > max + 1 ||
leftEnds[max + 1][need / 2] < min)
{
ok[i][c - 'a'] = true;
//System.out.println("ok " + i + " " + c);
}
}
}
/*for (int i = 0; i <= n; i++)
{
for (int j = n - 1; j > i; j--)
{
int midLength = sMax - pal[i][j - 1];
if (midLength % 2 == 0 &&
rightEnds[i][midLength / 2] > j)
{
ok[i][s.charAt(j) - 'a'] = true;
}
}
}
for (int i = n; i >= 0; i--)
{
for (int j = 0; j < i - 1; j++)
{
int midLength = sMax - pal[j + 1][i - 1];
if (midLength % 2 == 0 &&
leftEnds[i][midLength / 2] < j)
{
ok[i][s.charAt(j) - 'a'] = true;
}
}
}*/
if (k == 1)
{
if (sMax % 2 == 0)
{
for (int i = sMax / 2; i < n; i++)
{
if (rightEnds[i][sMax / 2] >= i)
{
for (int j = 0; j < 26; j++)
{
ok[i][j] = true;
}
}
}
}
else
{
/*int half = sMax / 2;
for (int i = 0; i < n; i++)
{
int ch = s.charAt(i) - 'a';
for (int j = i; j >= half; j--)
{
if (rightEnds[j][half] > i)
{
ok[j][ch] = true;
}
else
{
break;
}
}
for (int j = i + 1; j <= n - half; j++)
{
if (leftEnds[j][half] < i)
{
ok[j][ch] = true;
}
else
{
break;
}
}
}*/
}
}
int total = 0;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j < 26; j++)
{
if (ok[i][j])
{
total++;
}
}
}
return total;
}
private static short[][] computeRightEnds(String s)
{
short n = (short) s.length();
short ends[][] = new short[n + 1][n / 2 + 1];
for (int i = 0; i < ends.length; i++)
{
for (int j = 0; j < ends[i].length; j++)
{
ends[i][j] = -1;
}
}
ends[0][0] = n;
for (int len = 1; len <= n; len++)
{
ends[len][0] = n;
int i = n - 1;
while (i >= 0 && s.charAt(i) != s.charAt(len - 1))
{
i--;
}
for (int c = 1; c <= n / 2 && c <= len; c++)
{
ends[len][c] = (short) Math.max(-1, ends[len - 1][c]);
while (i >= ends[len - 1][c - 1])
{
i--;
while (i >= 0 && s.charAt(i) != s.charAt(len - 1))
{
i--;
}
}
if (i >= len)
{
ends[len][c] = (short) Math.max(ends[len][c], i);
}
}
}
return ends;
}
private static short[][] computeLeftEnds(String s)
{
short n = (short) s.length();
short ends[][] = new short[n + 1][n / 2 + 1];
for (int i = 0; i < ends.length; i++)
{
for (int j = 0; j < ends[i].length; j++)
{
ends[i][j] = n;
}
}
ends[n][0] = -1;
for (int k = n - 1; k >= 0; k--)
{
ends[k][0] = -1;
int i = 0;
while (i < n && s.charAt(i) != s.charAt(k))
{
i++;
}
for (int c = 1; c <= n / 2 && c <= n - k; c++)
{
ends[k][c] = (short) Math.min(n, ends[k + 1][c]);
while (i <= ends[k + 1][c - 1])
{
i++;
while (i < n && s.charAt(i) != s.charAt(k))
{
i++;
}
}
if (i < k)
{
ends[k][c] = (short) Math.min(ends[k][c], i);
}
}
}
return ends;
}
private static short[][] computePal(String s)
{
int n = s.length();
short pal[][] = new short[n][n];
for (int i = 0; i < n; i++)
{
pal[i][i] = 1;
}
for (int d = 1; d < n; d++)
{
for (int i = 0, j = d; j < n; i++, j++)
{
if (s.charAt(i) == s.charAt(j))
{
if (d == 1)
{
pal[i][j] = 2;
}
else
{
pal[i][j] = (short) (pal[i + 1][j - 1] + 2);
}
}
else
{
pal[i][j] = (short) Math.max(pal[i][j - 1], pal[i + 1][j]);
}
}
}
return pal;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int q = in.nextInt();
for(int a0 = 0; a0 < q; a0++){
int n = in.nextInt();
int k = in.nextInt();
String s = in.next();
int result = longestPalindromicSubsequence(s, k);
System.out.println(result);
}
in.close();
}
}
In C :
#include<stdio.h>
#define M 3005
int q, n, k;
char s[M];
int in[M][M], out[M][M];
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
scanf("%d", &q);
while(q--)
{
scanf("%d %d", &n, &k);
scanf("%s", s);
if( k == 0 )
{
printf("%d\n", ( n + 1 ) * 26);
continue;
}
if( k > 2 )
{
printf("0\n");
continue;
}
for( int l = 0 ; l < n ; l++ )
{
for( int i = 0 ; i + l < n ; i++ )
{
int j = i + l;
if( i == j )
{
in[i][j] = 1;
}
else if( s[i] == s[j] )
{
if( i + 1 < j )
{
in[i][j] = 2 + in[i+1][j-1];
}
else
{
in[i][j] = 2;
}
}
else
{
in[i][j] = max(in[i+1][j], in[i][j-1]);
}
}
}
for( int l = n - 1 ; l >= 0 ; l-- )
{
for( int i = 0 ; i + l < n ; i++ )
{
int j = i + l;
if( i == j )
{
if( 0 < i && j + 1 < n )
{
out[i][j] = 1 + out[i-1][j+1];
}
else
{
out[i][j] = 1;
}
}
else if( s[i] == s[j] )
{
if( 0 < i && j + 1 < n )
{
out[i][j] = 2 + out[i-1][j+1];
}
else
{
out[i][j] = 2;
}
}
else
{
out[i][j] = 0;
if( 0 < i )
{
out[i][j] = max(out[i][j], out[i-1][j]);
}
if( j + 1 < n )
{
out[i][j] = max(out[i][j], out[i][j+1]);
}
}
}
}
int cur = in[0][n-1], res = 0;
for( int i = 0 ; i <= n ; i++ )
{
for( char ch = 'a' ; ch <= 'z' ; ch++ )
{
int my = ( i == 0 || i == n ) ? 1 : 1 + out[i-1][i];
for( int j = 0 ; j < i && my < cur + k ; j++ )
{
if( s[j] == ch )
{
int cand = 2;
if( 0 < j && i < n )
{
cand += out[j-1][i];
}
if( j + 1 <= i - 1 )
{
cand += in[j+1][i-1];
}
my = max(my, cand);
}
}
for( int j = i ; j < n && my < cur + k ; j++ )
{
if( s[j] == ch )
{
int cand = 2;
if( 0 < i && j + 1 < n )
{
cand += out[i-1][j+1];
}
if( i <= j - 1 )
{
cand += in[i][j-1];
}
my = max(my, cand);
}
}
if( my >= cur + k )
{
res++;
}
}
}
printf("%d\n", res);
}
return 0;
}
View More Similar Problems
Direct Connections
Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do
View Solution →Subsequence Weighting
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =
View Solution →Kindergarten Adventures
Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti
View Solution →Mr. X and His Shots
A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M
View Solution →Jim and the Skyscrapers
Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space
View Solution →Palindromic Subsets
Consider a lowercase English alphabetic letter character denoted by c. A shift operation on some c turns it into the next letter in the alphabet. For example, and ,shift(a) = b , shift(e) = f, shift(z) = a . Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms: 1 i j t: All letters in the inclusive range from i t
View Solution →