Lexicographically smallest string with period K possible by replacing ' ? ' s from a given string | C ++ program for the above approach ; Function to modify the given string such that string S is a period of K ; Iterate over the range [ 0 , K ] ; Stores the frequency of the characters S [ i + j * K ] ; Iterate over the string with increment of K ; Print " - 1" ; Replace all characters of the string with ' ? ' to ' a ' to make it smallest ; Otherwise ; Find the character other than ' ? ' ; Replace all characters of the string with ' ? ' to character ch ; Clear the map M ; Return the modified string ; Driver Code
#include " bits / stdc + + . h " NEW_LINE using namespace std ; string modifyString ( string & S , int K ) { int N = S . length ( ) ; for ( int i = 0 ; i < K ; i ++ ) { map < char , int > M ; for ( int j = i ; j < N ; j += K ) { M [ S [ j ] ] ++ ; } if ( M . size ( ) > 2 ) { return " - 1" ; } else if ( M . size ( ) == 1 ) { if ( M [ ' ? ' ] != 0 ) { for ( int j = i ; j < N ; j += K ) { S [ j ] = ' a ' ; } } } else if ( M . size ( ) == 2 ) { char ch ; for ( auto & it : M ) { if ( it . first != ' ? ' ) { ch = it . first ; } } for ( int j = i ; j < N ; j += K ) { S [ j ] = ch ; } } M . clear ( ) ; } return S ; } int main ( ) { string S = " ab ? ? " ; int K = 2 ; cout << modifyString ( S , K ) ; return 0 ; }