Check if a String can be converted to Pangram in K changes
Given a String str containing only lowercase English alphabets and an integer K. The task is to check that whether the string can be converted to a Pangram by performing at most K changes. In one change we can remove any existing character and add a new character.
Pangram: A pangram is a sentence containing every letter in the English Alphabet.
Note: Given that length of string is greater than 26 always and in one operation we have to remove an existing element to add a new element.
Examples:
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.
Approach:
- Traverse the string character by character to keep track of all the characters present in the array using a boolean visit array.
- Using a variable count, traverse the visit array to keep count of the missing characters.
- If count value is less than or equal to K, print True.
- Else print False.
Below is the implementation of above approach:
C++
// 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 Codeint 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
// Java Program to check if a String can be // converted to Pangram by atmost k modificationspublic 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
# 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 Codeif __name__ == "__main__" : S = "thequickquickfoxmumpsoverthelazydog" k = 15 # function calling print(isPangram(S,k)) # This code is contributed by ANKITRAI1 |
C#
// 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 // 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?> |
Javascript
<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> |
Output
true
Complexity Analysis:
- Time Complexity: O(|S|) ,where S is the given string
- Space Complexity : O(26) ,to store characters.
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
