Sub | C ++ implementation of the approach ; Function that returns true if every lowercase character appears atmost once ; every character frequency must be not greater than one ; Function that returns the modified good string if possible ; If the length of the string is less than n ; Sub - strings of length 26 ; To store frequency of each character ; Get the frequency of each character in the current sub - string ; Check if we can get sub - string containing all the 26 characters ; Find which character is missing ; Fill with missing characters ; Find the next missing character ; Return the modified good string ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool valid ( int cnt [ ] ) { for ( int i = 0 ; i < 26 ; i ++ ) { if ( cnt [ i ] >= 2 ) return false ; } return true ; } string getGoodString ( string s , int n ) { if ( n < 26 ) return " - 1" ; for ( int i = 25 ; i < n ; i ++ ) { int cnt [ 26 ] = { 0 } ; for ( int j = i ; j >= i - 25 ; j -- ) { cnt [ s [ j ] - ' a ' ] ++ ; } if ( valid ( cnt ) ) { int cur = 0 ; while ( cnt [ cur ] > 0 ) cur ++ ; for ( int j = i - 25 ; j <= i ; j ++ ) { if ( s [ j ] == ' ? ' ) { s [ j ] = cur + ' a ' ; cur ++ ; while ( cnt [ cur ] > 0 ) cur ++ ; } } return s ; } } return " - 1" ; } int main ( ) { string s = " abcdefghijkl ? nopqrstuvwxy ? " ; int n = s . length ( ) ; cout << getGoodString ( s , n ) ; return 0 ; }