Given a lowercase string A of length N and an integer K, find the lexicographically smallest string B of the same length as A such that hamming distance between A and B is exactly K.
Examples:
Input : A = "pqrs", k = 1. Output : aqrs We can differ by at most one character. So we put 'a' in the beginning to make the result lexicographically smallest. Input : A = "pqrs", k = 2. Output : aars
We start from left to right, if the character at the current position of string A is ‘a’, then we assign the current position of string B character ‘a’. This position will not contribute towards the hamming distance. If character at this position in A is not equal to ‘a’, then also we will assign current position of string B character ‘a’, now this will contribute towards hamming distance and this can be done at most k times because Hamming distance has to be equal to K, if this is already done K times, we will assign this position of B same character as A.
If after the previous step, hamming distance between A and B is K, we are done otherwise we have to make more changes to B. Now we will start from right to left in B, and if character at the current position is equal to the corresponding character of A, change character of B to ‘b’, hence increasing the hamming distance by one, we will do it until hamming distance becomes equal to K.
Below is the implementation of this approach:
C++
// CPP program to find Lexicographically// smallest string whose hamming distance// from given string is exactly K#include <bits/stdc++.h>using namespace std;// function to find Lexicographically// smallest string with hamming distance kvoid findString(string str, int n, int k){ // If k is 0, output input string if (k == 0) { cout << str << endl; return; } // Copying input string into output // string string str2 = str; int p = 0; // Traverse all the character of the // string for (int i = 0; i < n; i++) { // If current character is not 'a' if (str2[i] != 'a') { // copy character 'a' to // output string str2[i] = 'a'; p++; // If hamming distance became k, // break; if (p == k) break; } } // If k is less than p if (p < k) { // Traversing string in reverse // order for (int i = n - 1; i >= 0; i--) if (str[i] == 'a') { str2[i] = 'b'; p++; if (p == k) break; } } cout << str2 << endl;}// Driven Programint main(){ string str = "pqrs"; int n = str.length(); int k = 2; findString(str, n, k); return 0;} |
Java
// Java program to find Lexicographically // smallest string whose hamming distance // from given string is exactly K class GFG {// function to find Lexicographically // smallest string with hamming distance k static void findString(String str, int n, int k) { // If k is 0, output input string if (k == 0) { System.out.println(str);; return; } // Copying input string into output // string String str2 = str; int p = 0; // Traverse all the character of the // string for (int i = 0; i < n; i++) { // If current character is not 'a' if (str2.charAt(i) != 'a') { // copy character 'a' to // output string str2 = str2.substring(0,i)+'a'+str2.substring(i+1); //str2[i] = 'a'; p++; // If hamming distance became k, // break; if (p == k) break; } } // If k is less than p if (p < k) { // Traversing string in reverse // order for (int i = n - 1; i >= 0; i--) if (str.charAt(i) == 'a') { str2 = str2.substring(0,i)+'b'+str2.substring(i+1); p++; if (p == k) break; } } System.out.println(str2); } // Driven Program public static void main(String[] args) { String str = "pqrs"; int n = str.length(); int k = 2; findString(str, n, k); }}// This code is contributed by 29AjayKumar |
Python 3
# Python 3 program to find Lexicographically# smallest string whose hamming distance# from the given string is exactly K# function to find Lexicographically# smallest string with hamming distance kdef findString(str, n, k): # If k is 0, output input string if (k == 0): print(str) return # Copying input string into output # string str2 = str p = 0 # Traverse all the character of the # string for i in range(0, n, 1): # If current character is not 'a' if (str2[i] != 'a'): # copy character 'a' to # output string str2 = str2.replace(str2[i], 'a') p += 1 # If hamming distance became k, # break; if (p == k): break # If k is less than p if (p < k): # Traversing string in reverse # order i = n - 1 while(i >= 0): if (str[i] == 'a'): str2 = str2.replace(str2[i], 'b') p += 1 if (p == k): break i -= 1 print(str2)# Driver Codeif __name__ == '__main__': str = "pqrs" n = len(str) k = 2 findString(str, n, k)# This code is contributed by # Surendra_Gangwar |
C#
// C# program to find Lexicographically // smallest string whose hamming distance // from given string is exactly K using System;class GFG{// function to find Lexicographically // smallest string with hamming distance k static void findString(String str, int n, int k) { // If k is 0, output input string if (k == 0) { Console.Write(str);; return; } // Copying input string into // output string String str2 = str; int p = 0; // Traverse all the character // of the string for (int i = 0; i < n; i++) { // If current character is not 'a' if (str2[i] != 'a') { // copy character 'a' to // output string str2 = str2.Substring(0, i) + 'a' + str2.Substring(i + 1); //str2[i] = 'a'; p++; // If hamming distance became k, // break; if (p == k) break; } } // If k is less than p if (p < k) { // Traversing string in reverse // order for (int i = n - 1; i >= 0; i--) if (str[i] == 'a') { str2 = str2.Substring(0, i) + 'b' + str2.Substring(i + 1); p++; if (p == k) break; } } Console.Write(str2); } // Driver Codepublic static void Main(){ String str = "pqrs"; int n = str.Length; int k = 2; findString(str, n, k); }}// This code is contributed by 29AjayKumar |
PHP
<?php// PHP program to find Lexicographically// smallest string whose hamming distance// from given string is exactly K// function to find Lexicographically// smallest string with hamming distance kfunction findString($str, $n, $k){ // If k is 0, output input string if ($k == 0) { echo $str . "\n"; return; } // Copying input string into // output string $str2 = $str; $p = 0; // Traverse all the character // of the string for ($i = 0; $i < $n; $i++) { // If current character is not 'a' if ($str2[$i] != 'a') { // copy character 'a' to // output string $str2[$i] = 'a'; $p++; // If hamming distance became k, // break; if ($p == $k) break; } } // If k is less than p if ($p < $k) { // Traversing string in reverse // order for ($i = $n - 1; $i >= 0; $i--) if ($str[$i] == 'a') { $str2[$i] = 'b'; $p++; if ($p == $k) break; } } echo $str2 . "\n";}// Driver Code$str = "pqrs";$n = strlen($str);$k = 2;findString($str, $n, $k);// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// javascript 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 function findString(str , n , k) { // If k is 0, output input string if (k == 0) { document.write(str);; return; } // Copying input string into output // string var str2 = str; var p = 0; // Traverse all the character of the // string for (i = 0; i < n; i++) { // If current character is not 'a' if (str2.charAt(i) != 'a') { // copy character 'a' to // output string str2 = str2.substring(0,i)+'a'+str2.substring(i+1); //str2[i] = 'a'; p++; // If hamming distance became k, // break; if (p == k) break; } } // If k is less than p if (p < k) { // Traversing string in reverse // order for (i = n - 1; i >= 0; i--) if (str.charAt(i) == 'a') { str2 = str2.substring(0,i)+'b'+str2.substring(i+1); p++; if (p == k) break; } } document.write(str2); } // Driven Program var str = "pqrs"; var n = str.length; var k = 2; findString(str, n, k); // This code is contributed by 29AjayKumar </script> |
Output
aars
Time Complexity: O(n)
Auxiliary Space: O(n)
This article is contributed by Aarti_Rathi and Anuj Chauhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
