La string lexicográficamente más pequeña cuya distancia de hamming desde la string dada es exactamente K

Dada una string A minúscula de longitud N y un número entero K , encuentre la string B lexicográficamente más pequeña de la misma longitud que A tal que la distancia de Hamming entre A y B sea exactamente K.

Ejemplos: 

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

Comenzamos de izquierda a derecha, si el carácter en la posición actual de la string A es ‘a’, entonces asignamos la posición actual de la string B al carácter ‘a’. Esta posición no contribuirá a la distancia de hamming. Si el carácter en esta posición en A no es igual a ‘a’, entonces también asignaremos la posición actual de la string B al carácter ‘a’, ahora esto contribuirá a la distancia de Hamming y esto se puede hacer como máximo k veces porque la distancia de Hamming tiene para ser igual a K, si esto ya se ha hecho K veces, le asignaremos a esta posición de B el mismo carácter que A. 

Si después del paso anterior, la distancia de hamming entre A y B es K, hemos terminado; de lo contrario, tenemos que hacer más cambios en B. Ahora comenzaremos de derecha a izquierda en B, y si el carácter en la posición actual es igual al carácter correspondiente de A, cambie el carácter de B a ‘b’, por lo tanto, aumentando la distancia de hamming en uno, lo haremos hasta que la distancia de hamming sea igual a K.

A continuación se muestra la implementación de este enfoque: 

// 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 k
void 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 Program
int main()
{
    string str = "pqrs";
    int n = str.length();
    int k = 2;
 
    findString(str, n, k);
 
    return 0;
}

// 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 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 k
def 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 Code
if __name__ == '__main__':
    str = "pqrs"
    n = len(str)
    k = 2
 
    findString(str, n, k)
 
# This code is contributed by
# Surendra_Gangwar

// 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 Code
public 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 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)
    {
        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
?>

<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>

aars

Complejidad temporal: O(n)
Espacio auxiliar: O(n)

Este artículo es una contribución de Aarti_Rathi y Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.