Count pairs of non overlapping Substrings of size K which form a palindromic String
Given a string S of length l, the task is to count the number of pairs of two non-overlapping substrings of length K of the string S, such that on joining the two non-overlapping substrings the resultant string is a palindrome.
Examples:
Input: S = “abcdbadc”, K = 2
Output: 2
Explanation: Possible substrings of length 2: ab, bc, cd, db, ba, ad, dc
- (ab, ba) => abba
- (cd, dc) => cddc
Input: S = “efjadcajfe”, K = 3
Output: 2
Explanation: Possible substrings of length 3: efj, fja, jad, adc, dca, caj, ajf, jfe
- (efj, jfe) => efjjfe
- (fja, ajf) => fjaajf
Approach: To solve the problem follow the below intuition:
A palindrome string is a string that if reversed will form the same original string. Also if you observe a palindromic string will always be even in length, hence it can be divided into two parts which will actually be mirror images of each other.
- This same idea of mirror images we apply to our approach. Since we have to find all substrings two nested loops will always be required.
- The outer loop will generate a substring of length K then the inner loop will again generate a substring of length K which will not overlap with the substring generated by the outer loop.
- Before starting the second loop we will reverse the outer string. Then we generate more non-overlapping substrings and check if any substring is equal to the outer reversed substring.
- If there is a match then definitely if we concatenate the inner string and original outer string then the newly formed string will be a palindromic string and the count for such strings will be incremented, else we continue our search.
Follow the below steps to solve the problem:
- Declare a counter variable to store the count.
- The outer loop starts from i = 0 and goes till the length of string l – K and in each iteration loop variable.
- A substring of length K is generated before the second loop begins and the reverse of the substring is stored in s1.
- The inner loop runs from i + K to l – K( the loop starts from i + k to avoid overlapping of substrings).
- A second substring of length K, s2 is generated which does not overlap with the first substring.
- Now check if the first string is equal to the second string.
- If yes then increment the counter else continue the loop
- exit outer loop
- exit inner loop
- Return the count
Below is the implementation of the above approach :
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Helper function to reverse a string string reverse(string s) { string ans = "" ; int l = s.length(); for ( int i = l - 1; i >= 0; i--) { ans.push_back(s[i]); } return ans; } // Function to return the count of the // pair of substring which are // palindrome to each other int myfunction(string s, int k) { // Store the count or the final answer int count = 0; for ( int i = 0; i <= s.length() - k; i++) { string s1 = s.substr(i, k); s1 = reverse(s1); string s2 = "" ; for ( int j = i + k; j <= s.length() - k; j++) { string s2 = s.substr(j, k); // If s1 is equal to s2 then // strings are mirror images // of each other if (s1 == s2) { count++; } } } return count; } // Driver function int main() { string s = "abcdbadc" ; int ans = myfunction(s, 2); // Function Call cout << "Number of such pairs is : " << ans; return 0; } |
Java
// Java code for the above approach: import java.util.*; class GFG { // Helper function to reverse a string public static String reverse(String s) { String ans = "" ; int l = s.length(); for ( int i = l - 1 ; i >= 0 ; i--) { ans += s.charAt(i); } return ans; } // Function to return the count of the // pair of substring which are // palindrome to each other public static int myfunction(String s, int k) { // Store the count or the final answer int count = 0 ; for ( int i = 0 ; i <= s.length() - k; i++) { String s1 = s.substring(i, i + k); s1 = reverse(s1); String s2 = "" ; for ( int j = i + k; j <= s.length() - k; j++) { s2 = s.substring(j, j + k); // If s1 is equal to s2 then // strings are mirror images // of each other if (s1.equals(s2)) { count++; } } } return count; } // Driver function public static void main(String[] args) { String s = "abcdbadc" ; int ans = myfunction(s, 2 ); // Function Call System.out.println( "Number of such pairs is : " + ans); } } // This Code is Contributed by Prasad Kandekar(prasad264) |
Python3
# Python code for the above approach: # Helper function to reverse a string def reverse(s): ans = "" l = len (s) for i in range (l - 1 , - 1 , - 1 ): ans + = s[i] return ans # Function to return the count of the # pair of substring which are # palindrome to each other def myfunction(s, k): # Store the count or the final answer count = 0 for i in range ( 0 , len (s) - k + 1 ): s1 = s[i:i + k] s1 = reverse(s1) s2 = "" for j in range (i + k, len (s) - k + 1 ): s2 = s[j:j + k] # If s1 is equal to s2 then # strings are mirror images # of each other if s1 = = s2: count + = 1 return count # Driver function def main(): s = "abcdbadc" ans = myfunction(s, 2 ) # Function Call print ( "Number of such pairs is : " , ans) if __name__ = = '__main__' : main() |
C#
// C# code for the above approach: using System; public class GFG { // Helper function to reverse a string static string Reverse( string s) { string ans = "" ; int l = s.Length; for ( int i = l - 1; i >= 0; i--) { ans += s[i]; } return ans; } // Function to return the count of the pair of substring // which are palindrome to each other static int Myfunction( string s, int k) { // Store the count or the final answer int count = 0; for ( int i = 0; i <= s.Length - k; i++) { string s1 = s.Substring(i, k); s1 = Reverse(s1); string s2 = "" ; for ( int j = i + k; j <= s.Length - k; j++) { s2 = s.Substring(j, k); // If s1 is equal to s2 then strings are // mirror images of each other if (s1.Equals(s2)) { count++; } } } return count; } static public void Main() { // Code string s = "abcdbadc" ; int ans = Myfunction(s, 2); // Function Call Console.WriteLine( "Number of such pairs is : " + ans); } } // This code is contributed by karthik. |
Javascript
// Helper function to reverse a string function reverse(s) { let ans = "" ; let l = s.length; for (let i = l - 1; i >= 0; i--) { ans += s[i]; } return ans; } // Function to return the count of the // pair of substring which are // palindrome to each other function myfunction(s, k) { // Store the count or the final answer let count = 0; for (let i = 0; i <= s.length - k; i++) { let s1 = s.slice(i, i + k); s1 = reverse(s1); let s2 = "" ; for (let j = i + k; j <= s.length - k; j++) { s2 = s.slice(j, j + k); // If s1 is equal to s2 then // strings are mirror images // of each other if (s1 === s2) { count += 1; } } } return count; } // Driver function function main() { let s = "abcdbadc" ; let ans = myfunction(s, 2); // Function Call console.log( "Number of such pairs is : " , ans); } main(); |
PHP
<?php // Helper function to reverse a string function reverse( $s ){ $ans = "" ; $l = strlen ( $s ); for ( $i = $l - 1; $i >= 0; $i --) { $ans .= $s [ $i ]; } return $ans ; } // Function to return the count of the pair of substring which are palindrome to each other function myfunction( $s , $k ) { // Store the count or the final answer $count = 0; for ( $i = 0; $i <= strlen ( $s ) - $k ; $i ++) { $s1 = substr ( $s , $i , $k ); $s1 = reverse( $s1 ); $s2 = "" ; for ( $j = $i + $k ; $j <= strlen ( $s ) - $k ; $j ++) { $s2 = substr ( $s , $j , $k ); // If s1 is equal to s2 then strings are mirror images of each other if ( $s1 == $s2 ) { $count ++; } } } return $count ; } // Driver function $s = "abcdbadc" ; $ans = myfunction( $s , 2); // Function Call echo "Number of such pairs is : " . $ans ; ?> |
Number of such pairs is : 2
Time Complexity: O ( (l – k) * (k + k) * (l – k) *k ) where l is the length of the string and k is the length of the substring.
Auxiliary Space: O ( 2*k ) where k is the length of the substring
Alternate Approach: To solve the problem follow the below idea:
This approach is more straightforward and simpler than the previous one. In this approach, we simply generate the outer string and the inner string but we won’t reverse the outer string. Instead, we concatenate the two strings and check if the newly formed string is a palindrome or not.
Follow the below steps to solve the problem:
- Declare a counter variable to store the count.
- The outer loop starts from i = 0 and goes till the length of string l – K and in each iteration loop variable.
- A substring of length K is generated before the second loop begins and stored in s1.
- The inner loop runs from i + K to l – K( the loop starts from i + K to avoid overlapping of substrings).
- A second substring of length K, s2 is generated which does not overlap with the first substring.
- Now concatenate the two substrings and check if the new string is a palindrome or not
- If yes then increment the counter else continue the loop
- exit outer loop
- exit inner loop
- Return the count
Below is the implementation for the above approach :
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Helper function to check for palindrome bool isPaldinrome(string s) { int l = s.length(); for ( int i = 0; i < l; i++) { if (s[i] != s[l - 1 - i]) return false ; } return true ; } // Function to return the count of the // pair of substring which on joining // form a palindromic string int myfunction(string s, int k) { // Store the count or the final answer int count = 0; for ( int i = 0; i <= s.length() - k; i++) { string s1 = s.substr(i, k); for ( int j = i + k; j <= s.length() - k; j++) { string s2 = s.substr(j, k); // Two strings are joined string s3 = s1 + s2; // If the joined string s3 is a // palindrome then increment // the counter if (isPaldinrome(s3)) { count++; } } } return count; } // Driver function int main() { string s = "abcdbadc" ; int ans = myfunction(s, 2); // Function Call cout << "Number of such pairs is : " << ans; return 0; } |
Java
// Java code for the above approach: import java.util.*; class GFG { // Helper function to check for palindrome public static boolean isPaldinrome(String s) { int l = s.length(); for ( int i = 0 ; i < l; i++) { if (s.charAt(i) != s.charAt(l - 1 - i)) return false ; } return true ; } // Function to return the count of the // pair of substring which on joining // form a palindromic string public static int myfunction(String s, int k) { // Store the count or the final answer int count = 0 ; for ( int i = 0 ; i <= s.length() - k; i++) { String s1 = s.substring(i, i + k); for ( int j = i + k; j <= s.length() - k; j++) { String s2 = s.substring(j, j + k); // Two strings are joined String s3 = s1 + s2; // If the joined string s3 is a // palindrome then increment // the counter if (isPaldinrome(s3)) { count++; } } } return count; } // Driver function public static void main(String[] args) { String s = "abcdbadc" ; int ans = myfunction(s, 2 ); // Function Call System.out.println( "Number of such pairs is : " + ans); } } // This Code is Contributed by Prasad Kandekar(prasad264) |
C#
// C# code addition for the above approach using System; public class GFG { // Helper function to check for palindrome public static bool IsPalindrome( string s) { int l = s.Length; for ( int i = 0; i < l; i++) { if (s[i] != s[l - 1 - i]) return false ; } return true ; } // Function to return the count of the pair of substring // which on joining form a palindromic string public static int MyFunction( string s, int k) { // Store the count or the final answer int count = 0; for ( int i = 0; i <= s.Length - k; i++) { string s1 = s.Substring(i, k); for ( int j = i + k; j <= s.Length - k; j++) { string s2 = s.Substring(j, k); // Two strings are joined string s3 = s1 + s2; // If the joined string s3 is a palindrome // then increment the counter if (IsPalindrome(s3)) { count++; } } } return count; } static public void Main() { // Code string s = "abcdbadc" ; int ans = MyFunction(s, 2); // Function Call Console.WriteLine( "Number of such pairs is : " + ans); } } // This code is contributed by sankar. |
Javascript
// JavaScript code for the above approach: // Helper function to check for palindrome function isPalindrome(s) { let l = s.length; for (let i = 0; i < l; i++) { if (s[i] !== s[l - 1 - i]) { return false ; } } return true ; } // Function to return the count of the // pair of substring which on joining // form a palindromic string function myfunction(s, k) { // Store the count or the final answer let count = 0; for (let i = 0; i <= s.length - k; i++) { let s1 = s.substr(i, k); for (let j = i + k; j <= s.length - k; j++) { let s2 = s.substr(j, k); // Two strings are joined let s3 = s1 + s2; // If the joined string s3 is a // palindrome then increment // the counter if (isPalindrome(s3)) { count++; } } } return count; } // Driver function function main() { let s = "abcdbadc" ; let ans = myfunction(s, 2); // Function Call console.log( "Number of such pairs is : " + ans); } main(); |
Python3
# Helper function to check for palindrome def isPalindrome(s): l = len (s) for i in range (l): if s[i] ! = s[l - 1 - i]: return False return True # Function to return the count of the pair of substring which on joining form a palindromic string def countPalindromicPairs(s, k): # Store the count or the final answer count = 0 for i in range ( len (s) - k + 1 ): s1 = s[i:i + k] for j in range (i + k, len (s) - k + 1 ): s2 = s[j:j + k] # Two strings are joined s3 = s1 + s2 # If the joined string s3 is a palindrome then increment the counter if isPalindrome(s3): count + = 1 return count # Driver function if __name__ = = "__main__" : s = "abcdbadc" ans = countPalindromicPairs(s, 2 ) # Function Call print ( "Number of such pairs is:" , ans) |
PHP
<?php // Helper function to check for palindrome function isPaldinrome( $s ) { $l = strlen ( $s ); for ( $i = 0; $i < $l ; $i ++) { if ( $s [ $i ] != $s [ $l - 1 - $i ]) return false; } return true; } // Function to return the count of the pair of substring which on joining form a palindromic string function myfunction( $s , $k ) { // Store the count or the final answer $count = 0; for ( $i = 0; $i <= strlen ( $s ) - $k ; $i ++) { $s1 = substr ( $s , $i , $k ); for ( $j = $i + $k ; $j <= strlen ( $s ) - $k ; $j ++) { $s2 = substr ( $s , $j , $k ); // Two strings are joined $s3 = $s1 . $s2 ; // If the joined string s3 is a palindrome then increment the counter if (isPaldinrome( $s3 )) { $count ++; } } } return $count ; } // Driver function $s = "abcdbadc" ; $ans = myfunction( $s , 2); // Function Call echo "Number of such pairs is : " . $ans ; ?> |
Number of such pairs is : 2
Time Complexity: O((l – k) * k * (l – k) *k + 2k) where l is the length of the string and k is the length of the substring.
Auxiliary Space: O(2*k) where k is the length of the substring
Contact Us