Count special palindromes in a String | Function to count special Palindromic susbstring ; store count of special Palindromic substring ; it will store the count of continues same char ; traverse string character from left to right ; store same character count ; count smiler character ; Case : 1 so total number of substring that we can generate are : K * ( K + 1 ) / 2 here K is sameCharCount ; store current same char count in sameChar [ ] array ; increment i ; Case 2 : Count all odd length Special Palindromic substring ; if current character is equal to previous one then we assign Previous same character count to current one ; case 2 : odd length ; subtract all single length substring ; Driver Code
def CountSpecialPalindrome ( str ) : NEW_LINE INDENT n = len ( str ) ; NEW_LINE result = 0 ; NEW_LINE sameChar = [ 0 ] * n ; NEW_LINE i = 0 ; NEW_LINE while ( i < n ) : NEW_LINE INDENT sameCharCount = 1 ; NEW_LINE j = i + 1 ; NEW_LINE while ( j < n ) : NEW_LINE INDENT if ( str [ i ] != str [ j ] ) : NEW_LINE INDENT break ; NEW_LINE DEDENT sameCharCount += 1 ; NEW_LINE j += 1 ; NEW_LINE DEDENT result += int ( sameCharCount * ( sameCharCount + 1 ) / 2 ) ; NEW_LINE sameChar [ i ] = sameCharCount ; NEW_LINE i = j ; NEW_LINE DEDENT for j in range ( 1 , n ) : NEW_LINE INDENT if ( str [ j ] == str [ j - 1 ] ) : NEW_LINE INDENT sameChar [ j ] = sameChar [ j - 1 ] ; NEW_LINE DEDENT if ( j > 0 and j < ( n - 1 ) and ( str [ j - 1 ] == str [ j + 1 ] and str [ j ] != str [ j - 1 ] ) ) : NEW_LINE INDENT result += ( sameChar [ j - 1 ] if ( sameChar [ j - 1 ] < sameChar [ j + 1 ] ) else sameChar [ j + 1 ] ) ; NEW_LINE DEDENT DEDENT return result - n ; NEW_LINE DEDENT str = " abccba " ; NEW_LINE print ( CountSpecialPalindrome ( str ) ) ; NEW_LINE