Given a string str and Q queries. Every query consists of two numbers L and R. The task is to print if the sub-string[L…R] is palindrome or not.
Examples:
Input: str = “abacccde”, Q[][] = {{0, 2}, {1, 2}, {2, 4}, {3, 5}}
Output:
Yes
No
No
YesInput: str = “abaaab”, Q[][] = {{0, 1}, {1, 5}}
Output:
No
Yes
Simple Approach: A naive approach is to check for every sub-string if it is palindrome or not. In the worst case, every query can take up to O(Q).
Efficient Approach: An efficient approach is to use Dynamic Programming to solve the above problem. We can initially create the DP table which stores if substring[i….j] is palindrome or not. We maintain a boolean dp[n][n] that is filled in a bottom-up manner. The value of dp[i][j] is true if the substring is a palindrome, otherwise false. To calculate dp[i][j], we first check the value of dp[i+1][j-1], if the value is true and s[i] is the same as s[j], then we make dp[i][j] true. Otherwise, the value of dp[i][j] is made false.
Now, for every query, check if dp[l][r] is true or not.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 100// Pre-processing functionvoid pre_process(bool dp[N][N], string s){ // Get the size of the string int n = s.size(); // Initially mark every // position as false for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) dp[i][j] = false; } // For the length for (int j = 1; j <= n; j++) { // Iterate for every index with // length j for (int i = 0; i <= n - j; i++) { // If the length is less than 2 if (j <= 2) { // If characters are equal if (s[i] == s[i + j - 1]) dp[i][i + j - 1] = true; } // Check for equal else if (s[i] == s[i + j - 1]) dp[i][i + j - 1] = dp[i + 1][i + j - 2]; } }}// Function to answer every query in O(1)void answerQuery(int l, int r, bool dp[N][N]){ if (dp[l][r]) cout << "Yes\n"; else cout << "No\n";}// Driver codeint main(){ string s = "abaaab"; bool dp[N][N]; pre_process(dp, s); int queries[][2] = { { 0, 1 }, { 1, 5 } }; int q = sizeof(queries) / sizeof(queries[0]); for (int i = 0; i < q; i++) answerQuery(queries[i][0], queries[i][1], dp); return 0;} |
Java
// Java implementation of the approachclass GFG { static int N = 100; // Pre-processing function static void pre_process(boolean dp[][], char[] s) { // Get the size of the string int n = s.length; // Initially mark every // position as false for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j] = false; } } // For the length for (int j = 1; j <= n; j++) { // Iterate for every index with // length j for (int i = 0; i <= n - j; i++) { // If the length is less than 2 if (j <= 2) { // If characters are equal if (s[i] == s[i + j - 1]) { dp[i][i + j - 1] = true; } } // Check for equal else if (s[i] == s[i + j - 1]) { dp[i][i + j - 1] = dp[i + 1][i + j - 2]; } } } } // Function to answer every query in O(1) static void answerQuery(int l, int r, boolean dp[][]) { if (dp[l][r]) { System.out.println("Yes"); } else { System.out.println("No"); } } // Driver code public static void main(String[] args) { String s = "abaaab"; boolean[][] dp = new boolean[N][N]; pre_process(dp, s.toCharArray()); int queries[][] = { { 0, 1 }, { 1, 5 } }; int q = queries.length; for (int i = 0; i < q; i++) { answerQuery(queries[i][0], queries[i][1], dp); } }}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approachN = 100# Pre-processing functiondef pre_process(dp, s): # Get the size of the string n = len(s) # Initially mark every # position as false for i in range(n): for j in range(n): dp[i][j] = False # For the length for j in range(1, n + 1): # Iterate for every index with # length j for i in range(n - j + 1): # If the length is less than 2 if (j <= 2): # If characters are equal if (s[i] == s[i + j - 1]): dp[i][i + j - 1] = True # Check for equal elif (s[i] == s[i + j - 1]): dp[i][i + j - 1] = dp[i + 1][i + j - 2]# Function to answer every query in O(1)def answerQuery(l, r, dp): if (dp[l][r]): print("Yes") else: print("No")# Driver codes = "abaaab"dp = [[0 for i in range(N)] for i in range(N)]pre_process(dp, s)queries = [[0, 1], [1, 5]]q = len(queries)for i in range(q): answerQuery(queries[i][0], queries[i][1], dp)# This code is contributed by mohit kumar |
C#
// C# implementation of the approachusing System;class GFG { static int N = 100; // Pre-processing function static void pre_process(bool[, ] dp, char[] s) { // Get the size of the string int n = s.Length; // Initially mark every // position as false for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i, j] = false; } } // For the length for (int j = 1; j <= n; j++) { // Iterate for every index with // length j for (int i = 0; i <= n - j; i++) { // If the length is less than 2 if (j <= 2) { // If characters are equal if (s[i] == s[i + j - 1]) { dp[i, i + j - 1] = true; } } // Check for equal else if (s[i] == s[i + j - 1]) { dp[i, i + j - 1] = dp[i + 1, i + j - 2]; } } } } // Function to answer every query in O(1) static void answerQuery(int l, int r, bool[, ] dp) { if (dp[l, r]) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } // Driver code public static void Main() { string s = "abaaab"; bool[, ] dp = new bool[N, N]; pre_process(dp, s.ToCharArray()); int[, ] queries = { { 0, 1 }, { 1, 5 } }; int q = queries.Length; for (int i = 0; i < q; i++) { answerQuery(queries[i, 0], queries[i, 1], dp); } }}// This code is contributed by Ankit. |
Javascript
<script> // javascript implementation of the approach var N = 100; // Pre-processing function function pre_process( dp, s) { // Get the size of the string var n = s.length; // Initially mark every // position as false for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { dp[i][j] = false; } } // For the length for (j = 1; j <= n; j++) { // Iterate for every index with // length j for (i = 0; i <= n - j; i++) { // If the length is less than 2 if (j <= 2) { // If characters are equal if (s[i] == s[i + j - 1]) { dp[i][i + j - 1] = true; } } // Check for equal else if (s[i] == s[i + j - 1]) { dp[i][i + j - 1] = dp[i + 1][i + j - 2]; } } } } // Function to answer every query in O(1) function answerQuery(l , r, dp) { if (dp[l][r]) { document.write("Yes<br/>"); } else { document.write("No<br/>"); } } // Driver code var s = "abaaab"; var dp = Array(N).fill().map(()=>Array(N).fill()); pre_process(dp, s); var queries = [ [ 0, 1 ], [ 1, 5 ] ]; var q = queries.length; for (i = 0; i < q; i++) { answerQuery(queries[i][0], queries[i][1], dp); }// This code contributed by Rajput-Ji</script> |
PHP
<?php// PHP implementation of the approach $N = 100;// Pre-processing function function pre_process($dp, $s) { // Get the size of the string $n = strlen($s); // Initially mark every // position as false for ($i = 0; $i < $n; $i++) { for ($j = 0; $j < $n; $j++) $dp[$i][$j] = false; } // For the length for ($j = 1; $j <= $n; $j++) { // Iterate for every index with // length j for ($i = 0; $i <= $n - $j; $i++) { // If the length is less than 2 if ($j <= 2) { // If characters are equal if ($s[$i] == $s[$i + $j - 1]) $dp[$i][$i + $j - 1] = true; } // Check for equal else if ($s[$i] == $s[$i + $j - 1]) $dp[$i][$i + $j - 1] = $dp[$i + 1][$i + $j - 2]; } } return $dp;} // Function to answer every query in O(1) function answerQuery($l, $r, $dp) { if ($dp[$l][$r]) echo "Yes\n"; else echo "No\n"; } // Driver code $s = "abaaab"; $dp = array(array());$dp = pre_process($dp, $s); $queries = array(array(0, 1), array(1, 5)); $q = count($queries); for ($i = 0; $i < $q; $i++) answerQuery($queries[$i][0], $queries[$i][1], $dp); // This code is contributed by Ryuga?> |
Output
No Yes
Time Complexity: O(N*N), as we are using nested loops for traversing N*N times. Where N is the length of the string.
Auxiliary Space: O(N*N), as we are using extra space for the dp matrix.
New Approach:- Another approach to check if a substring is a palindrome or not is to use the two-pointer technique. We can iterate from both ends of the substring and check if the characters at both ends are equal. If they are equal, we move the left pointer one step to the right and the right pointer one step to the left. If they are not equal, we can conclude that the substring is not a palindrome.
Algorithm:
- Define a function named isPalindrome which takes a string ‘s’, and two integers ‘l’ and ‘r’ as arguments.
- Inside the function, use a while loop to iterate from both ends of the substring, starting from l and r indices respectively.
- Check if the characters at both ends are equal. If they are not equal, return false.
- If we reach the middle of the substring, it means the substring is a palindrome, so return true.
- In the main function, initialize a string ‘s’ and an integer 2D array ‘queries’ which contains the indices of the substrings to be checked.
- Get the number of queries ‘q’ by dividing the size of the queries array by the size of a single query array.
- Iterate through the queries using a for loop and call the isPalindrome function for each query.
- If the isPalindrome function returns true, print “Yes”, else print “No”.
- The program ends after all the queries have been answered.
Here is the implementation of the two-pointer approach:
C++
#include <iostream>using namespace std;bool isPalindrome(string s, int l, int r) { while (l < r) { if (s[l] != s[r]) return false; l++; r--; } return true;}int main() { string s = "abaaab"; int queries[][2] = { { 0, 1 }, { 1, 5 } }; int q = sizeof(queries) / sizeof(queries[0]); for (int i = 0; i < q; i++) { int l = queries[i][0], r = queries[i][1]; if (isPalindrome(s, l, r)) cout << "Yes\n"; else cout << "No\n"; } return 0;} |
Java
public class Main { public static boolean isPalindrome(String s, int l, int r) { while (l < r) { if (s.charAt(l) != s.charAt(r)) return false; l++; r--; } return true; } public static void main(String[] args) { String s = "abaaab"; int[][] queries = { { 0, 1 }, { 1, 5 } }; int q = queries.length; for (int i = 0; i < q; i++) { int l = queries[i][0], r = queries[i][1]; if (isPalindrome(s, l, r)) System.out.println("Yes"); else System.out.println("No"); } }} |
Python
def is_palindrome(s, l, r): while l < r: if s[l] != s[r]: return False l += 1 r -= 1 return Trues = "abaaab"queries = [[0, 1], [1, 5]]q = len(queries)for i in range(q): l, r = queries[i] if is_palindrome(s, l, r): print("Yes") else: print("No") |
C#
// C# program to check if a substring is a palindromeusing System;class GFG{ // Function to check if a substring is a palindrome static bool IsPalindrome(string s, int l, int r) { while (l < r) { if (s[l] != s[r]) return false; l++; r--; } return true; }// Driver Code static void Main() { string s = "abaaab"; int[,] queries = { { 0, 1 }, { 1, 5 } }; int q = queries.GetLength(0); // Iterate over each query for (int i = 0; i < q; i++) { int l = queries[i, 0]; int r = queries[i, 1]; if (IsPalindrome(s, l, r)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } }} |
Javascript
// Function to check if a substring is a palindromefunction isPalindrome(s, l, r) { while (l < r) { if (s[l] !== s[r]) { return false; } l++; r--; } return true;}// Driver Code const s = "abaaab"; const queries = [[0, 1], [1, 5]]; const q = queries.length; // Iterate over each query for (let i = 0; i < q; i++) { const l = queries[i][0]; const r = queries[i][1]; if (isPalindrome(s, l, r)) { console.log("Yes"); } else { console.log("No"); } } |
Output:-
No
Yes
Time complexity:
– The function `isPalindrome()` takes O((r-l)/2) time to check if a substring is a palindrome or not.
– The for loop in the `main()` function runs q times and each iteration calls `isPalindrome()` function once.
– Therefore, the time complexity of the overall program is O(q*(r-l)/2) or simply O(q*r).
Auxiliary Space:
– The space used by the program is constant, independent of the size of the input string.
– Therefore, the auxiliary space complexity of the program is O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
