K-Pangrams

Given a string str and an integer k, return true if the string can be changed into a pangram after at most k operations, else return false.

A single operation consists of swapping an existing alphabetic character with any other lowercase alphabetic character.

Note – A pangram is a sentence containing every letter in the english alphabet.

Examples :

Input: str = "the quick brown fox jumps over the lazy dog", k = 0
Output: true
Explanation: the sentence contains all 26 characters and is already a pangram.

Input: str = "aaaaaaaaaaaaaaaaaaaaaaaaaa", k = 25 
Output: true
Explanation: The word contains 26 instances of 'a'. Since only 25 operations are allowed. We can keep 1 instance and change all others to make str a pangram.

Input: str = "a b c d e f g h i j k l m", k = 20
Output: false
Explanation: Since there are only 13 alphabetic characters in this case, no amount of swapping can produce a panagram here.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)  

Constraints:
1<= str.size() <= 10⁵
0<= k <= 50
str may contain duplicate characters
str contains only lowercase alphabets or spaces.

Approach 01

class Solution {
  public:

    bool kPangram(string str, int k) {
        str.erase(std::remove(str.begin(), str.end(), ' '), str.end());
        int n = str.length();
       
        if(n < 26) {
            return false;
        }
        
        if(k >= 25) {
            return true;
        } 

        string charSet = "abcdefghijklmnopqrstuvwxyz";

        for(int i = 0; i < n; i++) {
            size_t pos = charSet.find(str[i]);
            if(pos != string::npos) {
                charSet.erase(pos, 1);
            }
        }
       
        return(charSet.empty() or charSet.length() <= k);
       
    }
};

#User function Template for python3
class Solution:
    def kPangram(self,string, k):
        data = string.split(' ')
        string = ''.join(data)
        n = len(string)
        
        if(n<26):
            return False
            
        if(k>=25):
            return True

        charSet = "abcdefghijklmnopqrstuvwxyz"
        
        for i in range(n):
            npos = charSet.find(string[i])
            if(npos != -1):
                charSet = charSet[:npos] + charSet[npos+1:]
        
        return ((len(charSet) == 0) or (len(charSet) <= k))

Time Complexity

• Removing spaces:

  Removing spaces from the string takes \( O(n) \) time, where \( n \) is the length of the input string str.

• Checking if string length is less than 26:

  Checking the length of the string is an \( O(1) \) operation.

• Handling edge case for large k:

  Checking if k >= 25 is an \( O(1) \) operation.

• Finding and erasing characters:

  For each character in the string, the code searches for its position in charSet and erases it if found. This takes \( O(26 \cdot n) = O(n) \) time because the size of charSet is constant (26).

• Overall Time Complexity:

  The overall time complexity is \( O(n) \), where \( n \) is the length of the input string str.

Space Complexity

• Input string manipulation:

  Removing spaces from the string does not require additional space beyond the input string itself, so this takes \( O(1) \) extra space.

• Character set:

  The charSet string is a constant size of 26, so it uses \( O(1) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \) as the extra space used does not depend on the input size.