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

Code Explanation

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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