Sub | 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
< ? php function valid ( & $ cnt ) { for ( $ i = 0 ; $ i < 26 ; $ i ++ ) { if ( $ cnt [ $ i ] >= 2 ) return false ; } return true ; } function getGoodString ( $ s , $ n ) { if ( $ n < 26 ) return " - 1" ; for ( $ i = 25 ; $ i < $ n ; $ i ++ ) { $ cnt = array_fill ( 0 , 26 , NULL ) ; for ( $ j = $ i ; $ j >= $ i - 25 ; $ j -- ) { if ( $ s [ $ j ] != ' ? ' ) $ cnt [ ord ( $ s [ $ j ] ) - ord ( ' a ' ) ] ++ ; } if ( valid ( $ cnt ) ) { $ cur = 0 ; while ( $ cur < 26 && $ cnt [ $ cur ] > 0 ) $ cur ++ ; for ( $ j = $ i - 25 ; $ j <= $ i ; $ j ++ ) { if ( $ s [ $ j ] == ' ? ' ) { $ s [ $ j ] = chr ( $ cur + ord ( ' a ' ) ) ; $ cur ++ ; while ( $ cur < 26 && $ cnt [ $ cur ] > 0 ) $ cur ++ ; } } return $ s ; } } return " - 1" ; } $ s = " abcdefghijkl ? nopqrstuvwxy ? " ; $ n = strlen ( $ s ) ; echo getGoodString ( $ s , $ n ) ; ? >