Compruebe si una string se puede convertir a Pangram en K cambia

Dado un String str que contiene solo alfabetos ingleses en minúsculas y un número entero K . La tarea es verificar si la string se puede convertir a un Pangram realizando como máximo K cambios. En un cambio, podemos eliminar cualquier carácter existente y agregar un nuevo carácter.
Pangrama : Un pangrama es una oración que contiene todas las letras del alfabeto inglés.
Nota : dado que la longitud de la string siempre es mayor que 26 y en una operación tenemos que eliminar un elemento existente para agregar un nuevo elemento.
Ejemplos : 
 

Input : str = "qwqqwqeqqwdsdadsdasadsfsdsdsdasasas"
        K = 4
Output : False
Explanation : Making just 4 modifications in this string, 
it can't be changed to a pangram. 

Input : str = "qwqqwqeqqwdsdadsdasadsfsdsdsdasasas"
        K = 24
Output : True
Explanation : By making 19 modifications in the string, 
it can be changed to a pangram.

Acercarse: 
 

1. Recorra la string carácter por carácter para realizar un seguimiento de todos los caracteres presentes en la array utilizando una array de visita booleana.
2. Utilizando un conteo variable, recorra la array de visitas para llevar la cuenta de los caracteres que faltan.
3. Si el valor de conteo es menor o igual a K, imprima Verdadero.
4. De lo contrario, escriba Falso.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to check if a
// String can be converted
// to Pangram by atmost k modifications
#include<bits/stdc++.h>
using namespace std;
 
// Function to find if string
// can be converted to Pangram
// by atmost k modifications
bool isPangram(string S, int k)
{
    if (S.length() < 26)
        return false;
 
    // visit array to keep track
    // of all the characters
    // present in the array
    int visited[26];
 
    for(int i = 0; i < S.length(); i++)
        visited[S[i] - 'a'] = true;
 
    // A variable to keep count
    // of characters missing
    // in the string
    int count = 0;
 
    for(int i = 0; i < 26; i++)
    {
        if (!visited[i])
            count += 1;
    }
 
    // Comparison of count
    // with given value K
    if(count <= k )
        return true;
    return false;
}
         
// Driver Code
int main()
{
 
    string S = "thequickquickfoxmumpsoverthelazydog";
    int k = 15;
     
    // function calling
    isPangram(S, k) ? cout<< "true" :
                      cout<< "false";
 
    return 0;
}
 
// This code is contributed by ChitraNayal

// Java Program to check if a String can be
// converted to Pangram by atmost k modifications
 
public class GFG {
 
    // Function to find if string can be converted
    // to Pangram by atmost k modifications
    static boolean isPangram(String S, int k)
    {
        if (S.length() < 26)
            return false;
 
        // visit array to keep track of all
        // the characters present in the array
        boolean[] visited = new boolean[26];
 
        for (int i = 0; i < S.length(); i++) {
            visited[S.charAt(i) - 'a'] = true;
        }
 
        // A variable to keep count of
        // characters missing in the string
        int count = 0;
 
        for (int i = 0; i < 26; i++) {
            if (!visited[i])
                count++;
        }
         
        // Comparison of count with given value K
        if (count <= k)
            return true;
        return false;
    }
     
    // Driver code
    public static void main(String[] args)
    {
        String S = "thequickquickfoxmumpsoverthelazydog";
         
        int k = 15;
         
        System.out.print(isPangram(S, k));
    }
}

# Python 3 program to check
# if a String can be converted
# to Pangram by atmost k modifications
 
# Function to find if string
# can be converted to Pangram
# by atmost k modifications
def isPangram(S, k) :
 
    if len(S) < 26 :
        return False
 
    # visit array to keep track
    # of all the characters
    # present in the array
    visited = [0] * 26
 
    for char in S :
        visited[ord(char) - ord('a')] = True
 
    # A variable to keep count
    # of characters missing
    # in the string
    count = 0
 
    for i in range(26) :
 
        if visited[i] != True :
            count += 1
 
    # Comparison of count
    # with given value K
    if count <= k :
        return True
    return False
         
# Driver Code
if __name__ == "__main__" :
     
    S = "thequickquickfoxmumpsoverthelazydog"
    k = 15
     
    # function calling
    print(isPangram(S,k))
         
# This code is contributed by ANKITRAI1

// C# Program to check if a
// String can be converted to
// Pangram by atmost k modifications
using System;
 
class GFG
{
 
// Function to find if string
// can be converted to Pangram
// by atmost k modifications
static bool isPangram(String S, int k)
{
    if (S.Length < 26)
        return false;
 
    // visit array to keep track
    // of all the characters present
    // in the array
    bool[] visited = new bool[26];
 
    for (int i = 0; i < S.Length; i++)
    {
        visited[S[i] - 'a'] = true;
    }
 
    // A variable to keep count
    // of characters missing in
    // the string
    int count = 0;
 
    for (int i = 0; i < 26; i++)
    {
        if (!visited[i])
            count++;
    }
     
    // Comparison of count with
    // given value K
    if (count <= k)
        return true;
    return false;
}
 
// Driver code
public static void Main()
{
    string S = "thequickquickfoxmumpsoverthelazydog";
     
    int k = 15;
     
    Console.WriteLine(isPangram(S, k));
}
}
 
// This code is contributed
// by inder_verma.

<?php
// PHP program to check if a
// String can be converted
// to Pangram by atmost k modifications
 
// Function to find if string
// can be converted to Pangram
// by atmost k modifications
function isPangram($S, $k)
{
    if (strlen($S) < 26)
        return false;
 
    // visit array to keep track
    // of all the characters
    // present in the array
    $visited = array_fill(0, 26, NULL);
 
    for($i = 0; $i < strlen($S); $i++)
        $visited[ord($S[$i]) -
                 ord('a')] = true;
 
    // A variable to keep count
    // of characters missing
    // in the string
    $count = 0;
 
    for($i = 0; $i < 26; $i++)
    {
        if ($visited[$i] != true)
            $count += 1;
    }
 
    // Comparison of count
    // with given value K
    if ($count <= $k )
        return true;
    return false;
}
         
// Driver Code
$S = "thequickquickfoxmumpsoverthelazydog";
$k = 15;
     
// function calling
echo isPangram($S, $k)? "true" : "false";
     
// This code is contributed by ChitraNayal
?>

<script>
      // JavaScript Program to check if a
      // String can be converted to
      // Pangram by atmost k modifications
      // Function to find if string
      // can be converted to Pangram
      // by atmost k modifications
      function isPangram(S, k) {
        if (S.length < 26) return false;
 
        // visit array to keep track
        // of all the characters present
        // in the array
        var visited = new Array(26);
 
        for (var i = 0; i < S.length; i++) {
          visited[S[i].charCodeAt(0) - "a".charCodeAt(0)] = true;
        }
 
        // A variable to keep count
        // of characters missing in
        // the string
        var count = 0;
 
        for (var i = 0; i < 26; i++) {
          if (!visited[i]) count++;
        }
 
        // Comparison of count with
        // given value K
        if (count <= k) return true;
        return false;
      }
 
      // Driver code
      var S = "thequickquickfoxmumpsoverthelazydog";
      var k = 15;
 
      document.write(isPangram(S, k));
    </script>

true

Complejidad de tiempo: O(|S|), donde S es la string dada

Complejidad espacial: O(26), para almacenar caracteres.