Given a string str, the task is to count the number of ways a palindromic substring could be formed by the concatenation of three sub-strings x, y and z of the string str such that all of them are non-overlapping i.e. sub-string y occurs after substring x and sub-string z occurs after sub-string y.
Examples:
Input: str = “abca”
Output: 2
The two valid pairs are (“a”, “b”, “a”) and (“a”, “c”, “a”)
Input: str = “abba”
Output: 5
Approach: Find all the possible pairs of three non-overlapping sub-strings and for every pairs check whether the string generated by their concatenation is a palindrome or not. If yes then increment the count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if// s[i...j] + s[k...l] + s[p...q]// is a palindromebool isPalin(int i, int j, int k, int l, int p, int q, string s){ int start = i, end = q; while (start < end) { if (s[start] != s[end]) return false; start++; if (start == j + 1) start = k; end--; if (end == p - 1) end = l; } return true;}// Function to return the count// of valid sub-stringsint countSubStr(string s){ // To store the count of // required sub-strings int count = 0; int n = s.size(); // For choosing the first sub-string for (int i = 0; i < n - 2; i++) { for (int j = i; j < n - 2; j++) { // For choosing the second sub-string for (int k = j + 1; k < n - 1; k++) { for (int l = k; l < n - 1; l++) { // For choosing the third sub-string for (int p = l + 1; p < n; p++) { for (int q = p; q < n; q++) { // Check if the concatenation // is a palindrome if (isPalin(i, j, k, l, p, q, s)) { count++; } } } } } } } return count;}// Driver codeint main(){ string s = "abca"; cout << countSubStr(s); return 0;} |
Java
// Java implementation of the approachclass GFG { // Function that returns true if // s[i...j] + s[k...l] + s[p...q] // is a palindrome static boolean isPalin(int i, int j, int k, int l, int p, int q, String s) { int start = i, end = q; while (start < end) { if (s.charAt(start) != s.charAt(end)) { return false; } start++; if (start == j + 1) { start = k; } end--; if (end == p - 1) { end = l; } } return true; } // Function to return the count // of valid sub-strings static int countSubStr(String s) { // To store the count of // required sub-strings int count = 0; int n = s.length(); // For choosing the first sub-string for (int i = 0; i < n - 2; i++) { for (int j = i; j < n - 2; j++) { // For choosing the second sub-string for (int k = j + 1; k < n - 1; k++) { for (int l = k; l < n - 1; l++) { // For choosing the third sub-string for (int p = l + 1; p < n; p++) { for (int q = p; q < n; q++) { // Check if the concatenation // is a palindrome if (isPalin(i, j, k, l, p, q, s)) { count++; } } } } } } } return count; } // Driver code public static void main(String[] args) { String s = "abca"; System.out.println(countSubStr(s)); }}// This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function that returns true if # s[i...j] + s[k...l] + s[p...q] # is a palindrome def isPalin(i, j, k, l, p, q, s) : start = i; end = q; while (start < end) : if (s[start] != s[end]) : return False; start += 1; if (start == j + 1) : start = k; end -= 1; if (end == p - 1) : end = l; return True; # Function to return the count # of valid sub-strings def countSubStr(s) : # To store the count of # required sub-strings count = 0; n = len(s); # For choosing the first sub-string for i in range(n-2) : for j in range(i, n-2) : # For choosing the second sub-string for k in range(j + 1, n-1) : for l in range(k, n-1) : # For choosing the third sub-string for p in range(l + 1, n) : for q in range(p, n) : # Check if the concatenation # is a palindrome if (isPalin(i, j, k, l, p, q, s)) : count += 1; return count; # Driver code if __name__ == "__main__" : s = "abca"; print(countSubStr(s)); # This course is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG { // Function that returns true if // s[i...j] + s[k...l] + s[p...q] // is a palindrome static bool isPalin(int i, int j, int k, int l, int p, int q, String s) { int start = i, end = q; while (start < end) { if (s[start] != s[end]) { return false; } start++; if (start == j + 1) { start = k; } end--; if (end == p - 1) { end = l; } } return true; } // Function to return the count // of valid sub-strings static int countSubStr(String s) { // To store the count of // required sub-strings int count = 0; int n = s.Length; // For choosing the first sub-string for (int i = 0; i < n - 2; i++) { for (int j = i; j < n - 2; j++) { // For choosing the second sub-string for (int k = j + 1; k < n - 1; k++) { for (int l = k; l < n - 1; l++) { // For choosing the third sub-string for (int p = l + 1; p < n; p++) { for (int q = p; q < n; q++) { // Check if the concatenation // is a palindrome if (isPalin(i, j, k, l, p, q, s)) { count++; } } } } } } } return count; } // Driver code public static void Main(String[] args) { String s = "abca"; Console.WriteLine(countSubStr(s)); } } // This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if// s[i...j] + s[k...l] + s[p...q]// is a palindromefunction isPalin(i, j, k, l, p, q, s){ var start = i, end = q; while (start < end) { if (s[start] != s[end]) return false; start++; if (start == j + 1) start = k; end--; if (end == p - 1) end = l; } return true;}// Function to return the count// of valid sub-stringsfunction countSubStr(s){ // To store the count of // required sub-strings var count = 0; var n = s.length; // For choosing the first sub-string for (var i = 0; i < n - 2; i++) { for (var j = i; j < n - 2; j++) { // For choosing the second sub-string for (var k = j + 1; k < n - 1; k++) { for (var l = k; l < n - 1; l++) { // For choosing the third sub-string for (var p = l + 1; p < n; p++) { for (var q = p; q < n; q++) { // Check if the concatenation // is a palindrome if (isPalin(i, j, k, l, p, q, s)) { count++; } } } } } } } return count;}// Driver codevar s = "abca";document.write( countSubStr(s));// This code is contributed by famously.</script> |
Output:
2
Time Complexity: O(n7), where n is the length of the given string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
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!
