Checking if all the characters from an A-Z is present in the string

Question

A string is said to be complete if it contains all the characters from a to z. Given a string, check if it complete or not.

Input First line of the input contains the number of strings N. It is followed by N lines each contains a single string.

Output For each test case print "YES" if the string is complete, else print "NO"

Constraints 1 <= N <= 10 The length of the string is at max 100 and the string contains only the characters a to z.

Here are the two solutions that I wrote:

class TestClass {
    private static byte N;
    public static void main(String args[] ) throws Exception {
        BufferedReader keyboard = new BufferedReader(new InputStreamReader(
                System.in));
       N = Byte.parseByte(keyboard.readLine());
        for (byte i = 0; i < N; i++) {
            String testingString = keyboard.readLine();
            isCompleteString(testingString);
        }
    }

    private static void isCompleteString(String testingString) {
        String resultString= "";
        char[] toChar = testingString.toCharArray();
        int length = toChar.length;
        for (int i = 0; i < length; i++) {
            if(resultString.indexOf(toChar[i])==-1){
                resultString=resultString.concat(toChar[i]+"");

            }


        }

        if(resultString.length()==26)System.out.println("YES");
        else System.out.println("NO");
    }

}

This took 1.6469 secs against various inputs, while this code took:

class TestClass {
    private static byte N;
    public static void main(String args[] ) throws Exception {
        BufferedReader keyboard = new BufferedReader(new InputStreamReader(
                System.in));
       N = Byte.parseByte(keyboard.readLine());
        for (byte i = 0; i < N; i++) {
            String testingString = keyboard.readLine();
            isCompleteString(testingString);
        }
    }

    private static void isCompleteString(String testingString) {

        char[] toChar = testingString.toCharArray();
        int length = toChar.length;
        boolean[] findingAlphabet = new boolean[26];
        for (int i = 0; i < length; i++) {
            byte alphabets = (byte) toChar[i];
            findingAlphabet[122-alphabets]=true;

        }
        int count=0;
        for(boolean b:findingAlphabet){
            if(b)
            count++;
        }
        if(count==26)System.out.println("YES");
        else System.out.println("NO");
    }

}

1.5818 secs against various inputs.

How can I optimize these programs further (I have used BitSet)? What are other possible optimized methods of doing the same?

Answer 1

private static byte N;

We know that N<=100, but this is a very premature optimization. In theory, you're saving 3 bytes total. Actually, it'll get rounded up to a nearest multiple of 8 or whatever and you save nothing at all.

It's also no good idea top make everything static.

BufferedReader keyboard = new BufferedReader(new InputStreamReader(
            System.in));

But the input does not come from the keyboard. Or can you type 100 lines in two seconds? I'd call it in as I'm lazy, something like reader would be fine.

isCompleteString(testingString);

According to the name, isCompleteString returns boolean. And there should be a method doing just this. Coupling output with computation makes you method 100% non-reusable.

First version

    String resultString= "";

Switch on your warning to see unused variables.

    char[] toChar = testingString.toCharArray();
    int length = toChar.length;
    for (int i = 0; i < length; i++) {

This looks like a premature optimization. And toChar is a bad name as there's no char but char[]. The IDE proposes charArrays or chars, which is both better.

If you want to use a char[], then use simply

   for (char c : chars)

This is clearly non-optimal

        if(resultString.indexOf(toChar[i])==-1){
            resultString=resultString.concat(toChar[i]+"");
        }

for many reasons

• indexOf - you're running through the string for each char
• toChar[i]+"" creates a String from each char needlessly
• resultString.concat(...) creates a new String every time

You could use a StringBuilder here.

But creating a String only to measure it's length is plain wrong. You could count the chars instead.

But counting the chars is plain wrong too. If you want to know if a beer crate is full, do you count the bottles? Or do you if there's a bottle missing?

    if(resultString.length()==26)System.out.println("YES");
    else System.out.println("NO");

This should be written as

   System.out.println(resultString.length()==26 ? "YES" : "NO");

apart from that 1. there should be no resultString, 2. there should be a method computing and a method printing.

Second version

    boolean[] findingAlphabet = new boolean[26];

No good name. What about foundChars or simply found?

        byte alphabets = (byte) toChar[i];

What byte? Never use a byte, unless either it's exactly what's needed or you have a big bunch of them.

        findingAlphabet[122-alphabets]=true;

Nice obfuscation. What about

       found[chars[i] - 'a'] = true;

? And bottle counting again

    int count=0;
    for(boolean b:findingAlphabet){
        if(b)
        count++;
    }

This should be

    for (boolean b : found) {
        if (!b) {
            return false;
        }
    }
    return true;

How can I optimaize these programs further (I have used BitSet)?

You haven't. But BitSet is slower than a boolean[] (except when memory locality comes in play).

It looks like most of the time gets spend on IO. Not surprising, even the first solution with doing 26 times indexOf on a 100 chars string is not computationally intensive.

It could be sped up by avoiding strings and working with the input bytes directly. But I'd concentrate on readability first, otherwise it'll become a huge mess.

You may want to specify input encoding as US-ASCII as it's sufficient and much faster than UTF-8 which may be your platform default.

Answer 2

Declarations

The class should be public. The isCompleteString() function should probably be public as well, since it implements the primary functionality of the program.

String args[] is allowable. However, String[] args is considered more idiomatic in Java, and easier to read. (You wrote char[] toChar further down, which is good.)

Declaring throws Exception is a bit sloppy and mysterious. If you only need IOException, then declare throws IOException.

isCompleteString() prints its output rather than returning a boolean. It is a strong convention in Java that methods named isSomething(), hasSomething(), or canSomething() should return a boolean. Also, printing the output prevents you from writing unit tests or reusing the code.

main()

N should not be a static variable. It's just a loop counter within main(), and should therefore just be a local variable.

Using byte for N is weird. Why limit yourself to 127 test cases? Just use int, which is more natural, more scalable, and no less efficient.

java.util.Scanner offers a slightly nicer interface for reading lines from System.in.

public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
        for (int n = Integer.parseInt(scanner.nextLine()); n > 0; n--) {
            boolean complete = isCompleteString(scanner.nextLine());
            System.out.println(complete ? "YES" : "NO");
        }
    }
}

isCompleteString()

As you noticed, the second implementation is more efficient. Searching a string is less efficient than arithmetic and an array lookup. Concatenating a string is less efficient than setting one element of an array.

122-alphabets is weird and mysterious. alphabets - 'a' would work just as well, and the intention would be more obvious.

Your second implementation is not really using java.util.BitSet, but it does something similar in spirit. Note that you only need a set of 26 bits. Guess what? An int has 32 bits! The following solution should be even faster.

/**
 * Tests whether all characters 'a' to 'z' are present in a string.
 * Behavior is undefined if the string contains any character outside
 * the 'a'-'z' range.
 */
public static boolean isCompleteString(String string) {
    int seen = 0;
    for (char c : string.toCharArray()) {
        // 'a'=1, 'b'=2, 'c'=4, ..., 'z'=2^25
        seen |= 1 << (c - 'a');
    }
    // Are the 26 least-siginificant bits all set?
    return seen == (1 << 26) - 1;
}

Answer 3

1. Method name/return type

   private static void isCompleteString(String testingString)
   

   Usually, the is prefix is reserved for methods that return a boolean value, so that your caller code becomes:

   System.out.println(isCompleteString(testingString) ? "YES" : "NO");
   

   To nitpick, the purpose of this method is also not to find a "complete" String, but rather determine if it contains all letters of the English i.e. "US-ASCII" alphabet. A better name might be isPangram or containsEveryLetter.

2. Testing/timings

   As pointed out by @maaartinus's excellent answer, how are you getting the < 2 seconds for "various inputs"? What's your test size, and have you performed multiple runs to take an average of your test timings? Are you only testing your main method, or the time it takes for the JVM to start up, get ready to receive the user input from System.in, and then handle the output to System.out?

   This is where unit testing comes into play. Again, as mentioned in his answer, this is not a performance-intensive problem to begin with, so I'm not too sure as to why you have tagged it with performance.

Answer 4

You could try to count the already found chars. Something like below. Saves you the last loop and also processing of the rest of the string once all chars are found.

int distinctCharsCnt =0;
for (int i = 0; i < length; i++) 
{ 
    byte alphabets = (byte) toChar[i]; 
    int charIndex = 122-alphabets;
    if(!findingAlphabet[charIndex])
    {
         findingAlphaber[charIndex] = true;
         distinctCharsCnt++;
    }
    if(distinctCharsCnt == 26)
    { return true; }
}