Admission in Ninja Gram
Ninja is shifting to a new place named NinjaGram. To take admission to the new school, the teacher gives him a sentence and asks him to check whether the sentence is a pangram.

A word or a sentence is called a pangram if it contains all the English alphabet letters.

Since Ninja is new to programming, he doesn’t have much experience; he asks you to solve the problem. Can you help Ninja figure out whether the sentence is a pangram?

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The test cases follow. The first line of each test case contains a number ‘n’ denoting the number of characters in the string. The second line of each test case contains the string where the string characters can be both uppercase and lowercase.

Output Format:

For each test case, if Ninja managed to solve the problem, print “YES” else “NO”. Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Admission in Ninja Gram

Ninja is shifting to a new place named NinjaGram. To take admission to the new school, the teacher gives him a sentence and asks him to check whether the sentence is a pangram.

A word or a sentence is called a pangram if it contains all the English alphabet letters.

Since Ninja is new to programming, he doesn’t have much experience; he asks you to solve the problem. Can you help Ninja figure out whether the sentence is a pangram?

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The test cases follow.

The first line of each test case contains a number ‘n’ denoting the number of characters in the string.

The second line of each test case contains the string where the string characters can be both uppercase and lowercase.

Output Format:

For each test case, if Ninja managed to solve the problem, print “YES” else “NO”.

Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1<= T <= 50
1<= n <= 10^4


Where ’T’ is the number of test cases, ‘n’ denotes the number of characters in the string.

Time Limit: 1 sec

Accepted Answer

Step 1 : I have used hashing concept to map occurrence of english alphabet.
Step 2 : I used Counter array with size 26 to find count of every alphabet.
Step 3 : Traverse the array and if it's panagram append the output string with 1 else 0

Accepted Answer

Brute Force

The idea is to maintain a boolean array that will check for all the characters in the string.

The steps are as follows:

We will maintain a boolean visited array of size 26 and initialized with false, which will contain whether a particular character has been seen or not.
We will traverse a loop starting from ‘i’=0 and to the size of the string - 1:
- Whenever we see a character we mark it as true.
- To take care of all case characters, lowercase and uppercase are considered the same. So ‘A’ and ‘a’ are marked in index 0 and similarly ‘Z’ and ‘z’ are marked in index 25.
After iterating through all the characters of the string, we will check whether all the characters from ‘a’ to ‘z’ are marked or not.
If any character is not marked then return false as this is not a pangram. Otherwise return true.

Space Complexity: O(1)Explanation:

O(1), no extra space required.

As we are not using any extra space except for an array to maintain 26 characters. Hence, the overall space complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where N is the number of characters in the string.

We are traversing a loop only once and checking if all the 26 characters are present in the string. Hence, the overall time complexity is O(N).

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N denotes the number of characters in the string.



*/

bool ninjaGram(string & str) {

  int n = str.size();



  // Create an array to mark the characters present in the string

  vector < bool > visited(26, false);



  // For indexing in visited[]

  int idx;



  // Traverse all characters

  for (int i = 0; i < n; i++) {

      

    // If uppercase character, subtract 'A' to find index.

    if (str[i] >= 'A' && str[i] <= 'Z') {

      idx = str[i] - 'A';

    }

    

    // If lowercase character, subtract 'a' to find index.

    else if (str[i] >= 'a'

      and str[i] <= 'z') {

      idx = str[i] - 'a';

    }

    

    // If this character is other than english lowercase and uppercase characters.

    else {

      continue;

    }



    visited[idx] = true;

  }



  // Return false if any character is unmarked

  for (int i = 0; i < 26; i++) {

    if (visited[i] != true) {

      return false;

    }

  }



  // If all characters were present

  return true;

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N denotes the number of characters in the string.

'''



def ninjaGram(str):



    n = len(str)



    # Create an array to mark the characters

    # present in the string

    visited = [False for k in range(26)]



    # Traverse all characters

    for i in range(n):



        # If uppercase character, subtract 'A'

        # to find index.

        ascii1 = ord(str[i]) - ord('A')

        ascii2 = ord(str[i]) - ord('a')

        if (ascii1 >= 0 and ascii1 <= 25):

            idx = ascii1



        # If lowercase character, subtract 'a'

        # to find index.

        elif (ascii2 >= 0 and ascii2 <= 25):

            idx = ascii2



        # If this character is other than english

        # lowercase and uppercase characters.

        else:

            continue



        visited[idx] = True



    # Return false if any character is unmarked

    for i in range(26):

        if (visited[i] != True):

            return False



    # If all characters were present

    return True

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N denotes the number of characters in the string.



*/



public class Solution {



	public static boolean ninjaGram(String str) {



		int n = str.length();



		// Create an array to mark the characters

		// present in the string

		boolean visited[] = new boolean[26];

		// For indexing in visited[]

		int idx;



		// Traverse all characters

		for (int i = 0; i < n; i++) {

			// If uppercase character, subtract 'A'

			// to find index.

			int ascii = (int)str.charAt(i) - (int)('A');

			int ascii2 = (int)str.charAt(i) - (int)('a');

			if (ascii >= 0 && ascii <= 25) {

				idx = ascii;

			}



			// If lowercase character, subtract 'a'

			// to find index.

			else if (ascii2 >= 0 && ascii2 <= 25) {

				idx = ascii2;

			}



			// If this character is other than english

			// lowercase and uppercase characters.

			else {

				continue;

			}



			visited[idx] = true;

		}



		// Return false if any character is unmarked

		for (int i = 0; i < 26; i++) {

			if (visited[i] != true) {

				return false;

			}

		}



		// If all characters were present

		return true;

	}

}