Number of positions where a letter can be inserted such that a string becomes palindrome | Function to check if the string is palindrome ; to know the length of string ; if the given string is a palindrome ( Case - I ) ; Sub - case - III ) ; if ( n % 2 == 0 ) : if the length is even ; count = 2 * count + 1 sub - case - I ; count = 2 * count + 2 sub - case - II ; insertion point ; Case - I ; Case - II ; Driver code
def isPalindrome ( s , i , j ) : NEW_LINE INDENT p = j NEW_LINE for k in range ( i , p + 1 ) : NEW_LINE INDENT if ( s [ k ] != s [ p ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT p -= 1 NEW_LINE DEDENT return True NEW_LINE DEDENT def countWays ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE count = 0 NEW_LINE if ( isPalindrome ( s , 0 , n - 1 ) ) : NEW_LINE INDENT for i in range ( n // 2 , n ) : NEW_LINE INDENT if ( s [ i ] == s [ i + 1 ] ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT count += 1 NEW_LINE DEDENT else : NEW_LINE DEDENT else : NEW_LINE INDENT for i in range ( n // 2 ) : NEW_LINE INDENT if ( s [ i ] != s [ n - 1 - i ] ) : NEW_LINE INDENT j = n - 1 - i NEW_LINE if ( isPalindrome ( s , i , n - 2 - i ) ) : NEW_LINE INDENT for k in range ( i - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( s [ k ] != s [ j ] ) : NEW_LINE INDENT break NEW_LINE DEDENT count += 1 NEW_LINE DEDENT count += 1 NEW_LINE DEDENT if ( isPalindrome ( s , i + 1 , n - 1 - i ) ) : NEW_LINE INDENT for k in range ( n - i , n ) : NEW_LINE INDENT if ( s [ k ] != s [ i ] ) : NEW_LINE INDENT break NEW_LINE DEDENT count += 1 NEW_LINE DEDENT count += 1 NEW_LINE DEDENT break NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " abca " NEW_LINE print ( countWays ( s ) ) NEW_LINE DEDENT