Skip to content

Instantly share code, notes, and snippets.

@kkabdol
Created November 14, 2019 19:42
Show Gist options
  • Save kkabdol/184807ca808d3fb6f1ccf95f82ec6b0a to your computer and use it in GitHub Desktop.
Save kkabdol/184807ca808d3fb6f1ccf95f82ec6b0a to your computer and use it in GitHub Desktop.
Special palindromic substrings
// problem : https://www.hackerrank.com/challenges/special-palindrome-again/problem
long substrCount(int n, string s) {
long count = 0;
// 1st pass
vector<pair<char, int>> v;
char cur = 0;
for( auto ch : s )
{
if( cur == ch )
{
++( v.back().second );
}
else
{
cur = ch;
v.push_back( { ch, 1 } );
}
}
// 2nd pass
for( auto& p : v )
{
count += ( p.second + 1 ) * p.second / 2;
}
// 3rd pass
for( int i = 1; i < v.size( ) - 1; ++ i )
{
if( v[ i ].second == 1
&& v[ i - 1 ].first == v[ i + 1 ].first )
{
count += min( v[ i - 1 ].second, v[ i + 1 ].second );
}
}
return count;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment