Check if frequency of all characters can become same by one removal | C ++ program to get same frequency character string by removal of at most one char ; Utility method to get index of character ch in lower alphabet characters ; Returns true if all non - zero elements values are same ; get first non - zero element ; check equality of each element with variable same ; Returns true if we can make all character frequencies same ; fill frequency array ; if all frequencies are same , then return true ; Try decreasing frequency of all character by one and then check all equality of all non - zero frequencies ; Check character only if it occurs in str ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define M  26 NEW_LINE int getIdx ( char ch ) { return ( ch - ' a ' ) ; } bool allSame ( int freq [ ] , int N ) { int same ; int i ; for ( i = 0 ; i < N ; i ++ ) { if ( freq [ i ] > 0 ) { same = freq [ i ] ; break ; } } for ( int j = i + 1 ; j < N ; j ++ ) if ( freq [ j ] > 0 && freq [ j ] != same ) return false ; return true ; } bool possibleSameCharFreqByOneRemoval ( string str ) { int l = str . length ( ) ; int freq [ M ] = { 0 } ; for ( int i = 0 ; i < l ; i ++ ) freq [ getIdx ( str [ i ] ) ] ++ ; if ( allSame ( freq , M ) ) return true ; for ( char c = ' a ' ; c <= ' z ' ; c ++ ) { int i = getIdx ( c ) ; if ( freq [ i ] > 0 ) { freq [ i ] -- ; if ( allSame ( freq , M ) ) return true ; freq [ i ] ++ ; } } return false ; } int main ( ) { string str = " xyyzz " ; if ( possibleSameCharFreqByOneRemoval ( str ) ) cout << " Yes " ; else cout << " No " ; }