Lexicographically smallest string whose hamming distance from given string is exactly K | CPP program to find Lexicographically smallest string whose hamming distance from given string is exactly K ; function to find Lexicographically smallest string with hamming distance k ; If k is 0 , output input string ; Copying input string into output string ; Traverse all the character of the string ; If current character is not ' a ' ; copy character ' a ' to output string ; If hamming distance became k , break ; ; If k is less than p ; Traversing string in reverse order ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findString ( string str , int n , int k ) { if ( k == 0 ) { cout << str << endl ; return ; } string str2 = str ; int p = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( str2 [ i ] != ' a ' ) { str2 [ i ] = ' a ' ; p ++ ; if ( p == k ) break ; } } if ( p < k ) { for ( int i = n - 1 ; i >= 0 ; i -- ) if ( str [ i ] == ' a ' ) { str2 [ i ] = ' b ' ; p ++ ; if ( p == k ) break ; } } cout << str2 << endl ; } int main ( ) { string str = " pqrs " ; int n = str . length ( ) ; int k = 2 ; findString ( str , n , k ) ; return 0 ; }