Count special palindromes in a String | C ++ program to count special Palindromic substring ; 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 program to test above fun
#include <bits/stdc++.h> NEW_LINE using namespace std ; int CountSpecialPalindrome ( string str ) { int n = str . length ( ) ; int result = 0 ; int sameChar [ n ] = { 0 } ; int i = 0 ; while ( i < n ) { int sameCharCount = 1 ; int j = i + 1 ; while ( str [ i ] == str [ j ] && j < n ) sameCharCount ++ , j ++ ; result += ( sameCharCount * ( sameCharCount + 1 ) / 2 ) ; sameChar [ i ] = sameCharCount ; i = j ; } for ( int j = 1 ; j < n ; j ++ ) { if ( str [ j ] == str [ j - 1 ] ) sameChar [ j ] = sameChar [ j - 1 ] ; if ( j > 0 && j < ( n - 1 ) && ( str [ j - 1 ] == str [ j + 1 ] && str [ j ] != str [ j - 1 ] ) ) result += min ( sameChar [ j - 1 ] , sameChar [ j + 1 ] ) ; } return result - n ; } int main ( ) { string str = " abccba " ; cout << CountSpecialPalindrome ( str ) << endl ; return 0 ; }