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

5 abbac 2 1 4 2 4

Sample Output

YES NO

Explanation

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(System.in); int n = scan.nextInt(); String str = scan.next(); 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(); if(dp[left-1][right-1]) System.out.println("YES"); else System.out.println("NO"); } } }