Given a string str of small alphabetic characters other than this we will be given many substrings of this string in form of index tuples. We need to find out the count of the palindromic substrings in given substring range.
Examples:
Input : String str = "xyaabax"
Range1 = (3, 5)
Range2 = (2, 3)
Output : 4
3
For Range1, substring is "aba"
Count of palindromic substring in "aba" is
four : "a", "b", "aba", "a"
For Range2, substring is "aa"
Count of palindromic substring in "aa" is
3 : "a", "a", "aa"
Prerequisite : Count All Palindrome Sub-Strings in a String
We can solve this problem using dynamic programming. First we will make a 2D array isPalin, isPalin[i][j] will be 1 if string(i..j) is a palindrome otherwise it will be 0. After constructing isPalin we will construct another 2D array dp, dp[i][j] will tell the count of palindromic substring in string(i..j)
Now we can write the relation among isPalin and dp values as shown below,
// isPalin[i][j] will be 1 if ith and jth characters
// are equal and mid substring str(i+1..j-1) is also
// a palindrome
isPalin[i][j] = (str[i] == str[j]) and
(isPalin[i + 1][j – 1])
// Similar to set theory we can write the relation among
// dp values as,
// dp[i][j] will be addition of number of palindromes from
// i to j-1 and i+1 to j subtracting palindromes from i+1
// to j-1 because they are counted twice once in dp[i][j-1]
// and then in dp[i + 1][j] plus 1 if str(i..j) is also a
// palindrome
dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1] +
isPalin[i][j];
Total time complexity of solution will be O(length ^ 2) for constructing dp array then O(1) per query.
C++
// C++ program to query number of palindromic// substrings of a string in a range#include <bits/stdc++.h>using namespace std;#define M 50// Utility method to construct the dp arrayvoid constructDP(int dp[M][M], string str){ int l = str.length(); // declare 2D array isPalin, isPalin[i][j] will // be 1 if str(i..j) is palindrome int isPalin[l + 1][l + 1]; // initialize dp and isPalin array by zeros for (int i = 0; i <= l; i++) { for (int j = 0; j <= l; j++) { isPalin[i][j] = dp[i][j] = 0; } } // loop for starting index of range for (int i = l - 1; i >= 0; i--) { // initialize value for one character strings as 1 isPalin[i][i] = 1; dp[i][i] = 1; // loop for ending index of range for (int j = i + 1; j < l; j++) { /* isPalin[i][j] will be 1 if ith and jth characters are equal and mid substring str(i+1..j-1) is also a palindrome */ isPalin[i][j] = (str[i] == str[j] && (i + 1 > j - 1 || isPalin[i + 1][j - 1])); /* dp[i][j] will be addition of number of palindromes from i to j-1 and i+1 to j subtracting palindromes from i+1 to j-1 (as counted twice) plus 1 if str(i..j) is also a palindrome */ dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1] + isPalin[i][j]; } }}// method returns count of palindromic substring in range (l, r)int countOfPalindromeInRange(int dp[M][M], int l, int r){ return dp[l][r];}// Driver code to test above methodsint main(){ string str = "xyaabax"; int dp[M][M]; constructDP(dp, str); int l = 3; int r = 5; cout << countOfPalindromeInRange(dp, l, r); return 0;} |
Java
// Java program to query number of palindromic// substrings of a string in a rangeimport java.io.*;class GFG { // Function to construct the dp array static void constructDp(int dp[][], String str) { int l = str.length(); // declare 2D array isPalin, isPalin[i][j] will // be 1 if str(i..j) is palindrome int[][] isPalin = new int[l + 1][l + 1]; // initialize dp and isPalin array by zeros for (int i = 0; i <= l; i++) { for (int j = 0; j <= l; j++) { isPalin[i][j] = dp[i][j] = 0; } } // loop for starting index of range for (int i = l - 1; i >= 0; i--) { // initialize value for one character strings as 1 isPalin[i][i] = 1; dp[i][i] = 1; // loop for ending index of range for (int j = i + 1; j < l; j++) { /* isPalin[i][j] will be 1 if ith and jth characters are equal and mid substring str(i+1..j-1) is also a palindrome */ isPalin[i][j] = (str.charAt(i) == str.charAt(j) && (i + 1 > j - 1 || (isPalin[i + 1][j - 1]) != 0)) ? 1 : 0; /* dp[i][j] will be addition of number of palindromes from i to j-1 and i+1 to j subtracting palindromes from i+1 to j-1 (as counted twice) plus 1 if str(i..j) is also a palindrome */ dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1] + isPalin[i][j]; } } } // method returns count of palindromic substring in range (l, r) static int countOfPalindromeInRange(int dp[][], int l, int r) { return dp[l][r]; } // driver program public static void main(String args[]) { int MAX = 50; String str = "xyaabax"; int[][] dp = new int[MAX][MAX]; constructDp(dp, str); int l = 3; int r = 5; System.out.println(countOfPalindromeInRange(dp, l, r)); }}// Contributed by Pramod Kumar |
Python3
# Python3 program to query the number of # palindromic substrings of a string in a range M = 50# Utility method to construct the dp array def constructDP(dp, string): l = len(string) # declare 2D array isPalin, isPalin[i][j] # will be 1 if str(i..j) is palindrome # and initialize it with zero isPalin = [[0 for i in range(l + 1)] for j in range(l + 1)] # loop for starting index of range for i in range(l - 1, -1, -1): # initialize value for one # character strings as 1 isPalin[i][i], dp[i][i] = 1, 1 # loop for ending index of range for j in range(i + 1, l): # isPalin[i][j] will be 1 if ith and jth # characters are equal and mid substring # str(i+1..j-1) is also a palindrome isPalin[i][j] = (string[i] == string[j] and (i + 1 > j - 1 or isPalin[i + 1][j - 1])) # dp[i][j] will be addition of number # of palindromes from i to j-1 and i+1 # to j subtracting palindromes from i+1 # to j-1 (as counted twice) plus 1 if # str(i..j) is also a palindrome dp[i][j] = (dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1] + isPalin[i][j]) # Method returns count of palindromic # substring in range (l, r) def countOfPalindromeInRange(dp, l, r): return dp[l][r] # Driver codeif __name__ == "__main__": string = "xyaabax" dp = [[0 for i in range(M)] for j in range(M)] constructDP(dp, string) l, r = 3, 5 print(countOfPalindromeInRange(dp, l, r))# This code is contributed by Rituraj Jain |
C#
// C# program to query number of palindromic// substrings of a string in a rangeusing System;class GFG { // Function to construct the dp array static void constructDp(int[, ] dp, string str) { int l = str.Length; // declare 2D array isPalin, isPalin[i][j] // will be 1 if str(i..j) is palindrome int[, ] isPalin = new int[l + 1, l + 1]; // initialize dp and isPalin array by zeros for (int i = 0; i <= l; i++) { for (int j = 0; j <= l; j++) { isPalin[i, j] = dp[i, j] = 0; } } // loop for starting index of range for (int i = l - 1; i >= 0; i--) { // initialize value for one // character strings as 1 isPalin[i, i] = 1; dp[i, i] = 1; // loop for ending index of range for (int j = i + 1; j < l; j++) { /* isPalin[i][j] will be 1 if ith and jth characters are equal and mid substring str(i+1..j-1) is also a palindrome*/ isPalin[i, j] = (str[i] == str[j] && (i + 1 > j - 1 || (isPalin[i + 1, j - 1]) != 0)) ? 1 : 0; /* dp[i][j] will be addition of number of palindromes from i to j-1 and i+1 to j subtracting palindromes from i+1 to j-1 (as counted twice) plus 1 if str(i..j) is also a palindrome */ dp[i, j] = dp[i, j - 1] + dp[i + 1, j] - dp[i + 1, j - 1] + isPalin[i, j]; } } } // method returns count of palindromic // substring in range (l, r) static int countOfPalindromeInRange(int[, ] dp, int l, int r) { return dp[l, r]; } // driver program public static void Main() { int MAX = 50; string str = "xyaabax"; int[, ] dp = new int[MAX, MAX]; constructDp(dp, str); int l = 3; int r = 5; Console.WriteLine(countOfPalindromeInRange(dp, l, r)); }}// This code is contributed by vt_m. |
PHP
<?php// PHP program to query number of palindromic // substrings of a string in a range $GLOBALS['M'] = 50; // Utility method to construct the dp array function constructDP($dp, $str) { $l = strlen($str); // declare 2D array isPalin, isPalin[i][j] // will be 1 if str(i..j) is palindrome $isPalin = array(array()); // initialize dp and isPalin array by zeros for ($i = 0; $i <= $l; $i++) { for ($j = 0; $j <= $l; $j++) { $isPalin[$i][$j] = $dp[$i][$j] = 0; } } // loop for starting index of range for ($i = $l - 1; $i >= 0; $i--) { // initialize value for one character // strings as 1 $isPalin[$i][$i] = 1; $dp[$i][$i] = 1; // loop for ending index of range for ($j = $i + 1; $j < $l; $j++) { /* isPalin[i][j] will be 1 if ith and jth characters are equal and mid substring str(i+1..j-1) is also a palindrome */ $isPalin[$i][$j] = ($str[$i] == $str[$j] && ($i + 1 > $j - 1 || $isPalin[$i + 1][$j - 1])); /* dp[i][j] will be addition of number of palindromes from i to j-1 and i+1 to j subtracting palindromes from i+1 to j-1 (as counted twice) plus 1 if str(i..j) is also a palindrome */ $dp[$i][$j] = $dp[$i][$j - 1] + $dp[$i + 1][$j] - $dp[$i + 1][$j - 1] + $isPalin[$i][$j]; } } return $dp ;} // method returns count of palindromic// substring in range (l, r) function countOfPalindromeInRange($dp, $l, $r) { return $dp[$l][$r]; } // Driver code$str = "xyaabax"; $dp = array(array());for($i = 0; $i < $GLOBALS['M']; $i++ ) for($j = 0; $j < $GLOBALS['M']; $j++) $dp[$i][$j] = 0; $dp = constructDP($dp, $str); $l = 3; $r = 5; echo countOfPalindromeInRange($dp, $l, $r);// This code is contributed by Ryuga?> |
Javascript
<script> // Javascript program to query number of palindromic // substrings of a string in a range // Function to construct the dp array function constructDp(dp, str) { let l = str.length; // declare 2D array isPalin, isPalin[i][j] will // be 1 if str(i..j) is palindrome let isPalin = new Array(l + 1); // initialize dp and isPalin array by zeros for (let i = 0; i <= l; i++) { isPalin[i] = new Array(l + 1); for (let j = 0; j <= l; j++) { isPalin[i][j] = dp[i][j] = 0; } } // loop for starting index of range for (let i = l - 1; i >= 0; i--) { // initialize value for one character strings as 1 isPalin[i][i] = 1; dp[i][i] = 1; // loop for ending index of range for (let j = i + 1; j < l; j++) { /* isPalin[i][j] will be 1 if ith and jth characters are equal and mid substring str(i+1..j-1) is also a palindrome */ isPalin[i][j] = (str[i] == str[j] && (i + 1 > j - 1 || (isPalin[i + 1][j - 1]) != 0)) ? 1 : 0; /* dp[i][j] will be addition of number of palindromes from i to j-1 and i+1 to j subtracting palindromes from i+1 to j-1 (as counted twice) plus 1 if str(i..j) is also a palindrome */ dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1] + isPalin[i][j]; } } } // method returns count of palindromic substring in range (l, r) function countOfPalindromeInRange(dp, l, r) { return dp[l][r]; } let MAX = 50; let str = "xyaabax"; let dp = new Array(MAX); for (let i = 0; i < MAX; i++) { dp[i] = new Array(MAX); for (let j = 0; j < MAX; j++) { dp[i][j] = 0; } } constructDp(dp, str); let l = 3; let r = 5; document.write(countOfPalindromeInRange(dp, l, r));</script> |
Output
4
Time complexity : O(l2)
Auxiliary Space : O(l2)
This article is contributed by Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
