K-Pangrams

JavaView on GFG

Time: O(n)

Space: O(26)

Intuition

Check if string can be made a pangram (all 26 letters present) by adding at most k characters.

Algorithm

1Count distinct letters in string. Missing = 26 - distinct. If missing <= k: yes.

Common Pitfalls

•Count unique letters using set or frequency array. Simple O(n) scan.

K-Pangrams.java

Java

// Approach: Count missing letters (ones not in string). A k-pangram needs at most k additional unique letters.
// Time: O(n) Space: O(26)
class Solution {
    boolean kPangram(String str, int k) {
        int n = str.length();

        if (n < 26)
            return false;

        int cnt = 0, cntSpaces = 0;
        int[] ch = new int[26];

        for (int i = 0; i < n; i++) {
            char c = str.charAt(i);

            if (Character.isLowerCase(c)) {
                ch[c - 'a']++;

                if (ch[c - 'a'] == 1)
                    cnt++;
            } else
                cntSpaces++;
        }

        int value = n - (cntSpaces + cnt);
        int remainLC = 26 - cnt;

        if (value >= remainLC && k >= remainLC)
            return true;

        return false;
    }
}

Was this solution helpful?