Count pairs of non overlapping Substrings of size K which form a palindromic String – GeeksforGeeks

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 : 

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 : 

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