Number of positions where a letter can be inserted such that a string becomes palindrome
Given a string str, we need to find the no. of positions where a letter(lowercase) can be inserted so that string becomes a palindrome.
Examples:
Input : str = "abca" Output : possible palindromic strings: 1) acbca (at position 2) 2) abcba (at position 4) Hence, the output is 2. Input : str = "aaa" Output : possible palindromic strings: 1) aaaa 2) aaaa 3) aaaa 4) aaaa Hence, the output is 4.
Naive Approach: This approach is to insert all 26 alphabets at every position possible i.e., N+1 positions and check at every position if this insertion makes it a palindrome and increase the count.
Efficient Approach: First you have to observe that we have to make insertion only at the point when the character at that point violates the palindrome condition i.e., . Now, there will be Two cases based on the above fact:
Case I: What if the given string is already a palindrome
Then we can only insert at the position such that the insertion does not violate the palindrome.
- If the length is even then we can always insert any letter in the middle.
- If the length is odd then we can insert the letter which is in middle, to the left or right to it.
- In both the cases we can insert the letter which is in middle(let it be ‘CH’), at positions equals to:
(no.of consecutive CH’s to the left of middle letter)*2.Case II: If it is not a palindrome
As mentioned above we should start inserting at position where , So we increase the count and check for the cases if insertion at any other position makes it a palindrome.
- If is a palindrome, then we can insert* at any position before until , K in range .(*letter = S[N-i-1])
- If is a palindrome, then we can insert* at any position after until , K in range .(*letter = S[i])
In all the cases we keep increasing the count.
Implementation:
C++
// CPP code to find the no.of positions where a // letter can be inserted to make it a palindrome #include <bits/stdc++.h> using namespace std; // Function to check if the string is palindrome bool isPalindrome(string &s, int i, int j) { int p = j; for ( int k = i; k <= p; k++) { if (s[k] != s[p]) return false ; p--; } return true ; } int countWays(string &s) { // to know the length of string int n = s.length(); int count = 0; // if the given string is a palindrome(Case-I) if (isPalindrome(s, 0, n - 1)) { // Sub-case-III) for ( int i = n / 2; i < n; i++) { if (s[i] == s[i + 1]) count++; else break ; } if (n % 2 == 0) // if the length is even { count++; count = 2 * count + 1; // sub-case-I } else count = 2 * count + 2; // sub-case-II } else { for ( int i = 0; i < n / 2; i++) { // insertion point if (s[i] != s[n - 1 - i]) { int j = n - 1 - i; // Case-I if (isPalindrome(s, i, n - 2 - i)) { for ( int k = i - 1; k >= 0; k--) { if (s[k] != s[j]) break ; count++; } count++; } // Case-II if (isPalindrome(s, i + 1, n - 1 - i)) { for ( int k = n - i; k < n; k++) { if (s[k] != s[i]) break ; count++; } count++; } break ; } } } return count; } // Driver code int main() { string s = "abca" ; cout << countWays(s) << endl; return 0; } |
Java
// Java code to find the no.of positions where a // letter can be inserted to make it a palindrome import java.io.*; class GFG { // Function to check if the string is palindrome static boolean isPalindrome(String s, int i, int j) { int p = j; for ( int k = i; k <= p; k++) { if (s.charAt(k) != s.charAt(p)) return false ; p--; } return true ; } static int countWays(String s) { // to know the length of string int n = s.length(); int count = 0 ; // if the given string is a palindrome(Case-I) if (isPalindrome(s, 0 , n - 1 )) { // Sub-case-III) for ( int i = n / 2 ; i < n; i++) { if (s.charAt(i) == s.charAt(i + 1 )) count++; else break ; } if (n % 2 == 0 ) // if the length is even { count++; count = 2 * count + 1 ; // sub-case-I } else count = 2 * count + 2 ; // sub-case-II } else { for ( int i = 0 ; i < n / 2 ; i++) { // insertion point if (s.charAt(i) != s.charAt(n - 1 - i)) { int j = n - 1 - i; // Case-I if (isPalindrome(s, i, n - 2 - i)) { for ( int k = i - 1 ; k >= 0 ; k--) { if (s.charAt(k) != s.charAt(j)) break ; count++; } count++; } // Case-II if (isPalindrome(s, i + 1 , n - 1 - i)) { for ( int k = n - i; k < n; k++) { if (s.charAt(k) != s.charAt(i)) break ; count++; } count++; } break ; } } } return count; } // Driver code public static void main(String[] args) { String s = "abca" ; System.out.println(countWays(s)); } } // This code is contributed by vt_m. |
Python 3
# Python 3 code to find the no.of positions # where a letter can be inserted to make it # a palindrome # Function to check if the string # is palindrome def isPalindrome(s, i, j): p = j for k in range (i, p + 1 ): if (s[k] ! = s[p]): return False p - = 1 return True def countWays(s): # to know the length of string n = len (s) count = 0 # if the given string is a palindrome(Case-I) if (isPalindrome(s, 0 , n - 1 )) : # Sub-case-III) for i in range (n / / 2 , n): if (s[i] = = s[i + 1 ]): count + = 1 else : break if (n % 2 = = 0 ): # if the length is even count + = 1 count = 2 * count + 1 # sub-case-I else : count = 2 * count + 2 # sub-case-II else : for i in range (n / / 2 ) : # insertion point if (s[i] ! = s[n - 1 - i]) : j = n - 1 - i # Case-I if (isPalindrome(s, i, n - 2 - i)) : for k in range (i - 1 , - 1 , - 1 ): if (s[k] ! = s[j]): break count + = 1 count + = 1 # Case-II if (isPalindrome(s, i + 1 , n - 1 - i)) : for k in range (n - i, n) : if (s[k] ! = s[i]): break count + = 1 count + = 1 break return count # Driver code if __name__ = = "__main__" : s = "abca" print (countWays(s)) # This code is contributed by ita_c |
C#
PHP
Javascript
Output
2