Palindromic Queries

Given a string s and m queries . Each query consists of (l,r) where 1 <= l <= r <= n(size of string).

You need to print whether l to r is a palindromic string or not.

A string can be called palindrome if its reverse is same as itself . Ex – “aba” .Input Format

First line contains n Second lines contains a string of length n. Next line contains m where m is the number of queries . Next m lines contains two integers l,r as described in the question.Constraints

n <= 1000

m <= 100000Output Format

for every query from l to r print “YES” if s[l…..r] is palindrome else print “NO” without quotes in a new line.Sample Input

1 4
2 4

Sample Output



s[1….4]=”abba”, it is a palindrome.

Solution – Java Program

import java.util.*;
public class Main {
    public static void main (String args[]) {
		Scanner scan = new Scanner(;

		int n = scan.nextInt();

  		String str =;

		int t = scan.nextInt();

		char[] c = str.toCharArray();

        boolean[][] dp = new boolean[n][n];

        for(int col=1;col<=n;col++)
            for(int row=0;row<=n-col;row++)
                if(col <= 2)
                    if(c[row] == c[row+col-1])
                        dp[row][row+col-1] = true;
                else if(c[row] == c[row+col-1])
                    dp[row][row+col-1] = dp[row+1][row+col-2];
		while(t-- > 0)
			int left = scan.nextInt();
			int right = scan.nextInt();

Code Explanation

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s