Counting occurrences of a character in a string

Question

Scenario "The Semantic Mind-Reader!" browser known as jhool is known as mind-reader for a reason. Here's why:

You don't need to type 'www.' to open a website anymore. Though, you still need to type '.com' to open a website. The browser predicts ALL THE VOWELS in the name of the website. (Not '.com', though. Again!) Obviously, this means you can type the name of a website faster and save some time.

Input format: The first line contains tc, the number of test cases. The second line contains the name of websites, as a string.

Output format: You have to print the ratio of characters you would have typed in Jhool's browser, to your normal browser.

Constraints:
1 <= tc <= 100
1 <= Length of the website <= 200

NOTE: You do NOT need to print the output in its lowest format. You should print in its original fraction format. The names of all the websites will be in small case only.

Every string will start from www. and end with .com, so well!

Sample Input

 2
www.google.com
www.hackerearth.com

Sample Output

7/14
11/19

Explanation Consider the first case: In Jhool's browser, you'll only have to type: ggl.com (7 characters) while in a normal browser, you'll have to type www.google.com, which is 14 characters.

Here is my solution:

import java.util.Scanner;
class TestClass {
    public static void main(String args[] ) throws Exception {
        Scanner keyboard=new Scanner(System.in);
        int t=keyboard.nextInt();
        keyboard.nextLine();
        while(t!=0){

            String s= keyboard.nextLine();

            int len=s.length();
            int count=0;
            for(int i=4;i<len-4;i++){
                if(s.substring(i,i+1).matches("[aeiouAEIOU]"))
                    count++;
            }
            System.out.println(len-count-4+"/"+len);
            t--;
        }
    }
}

But the above took around 2.4583 sec in total for against the 7 set of input.

input 1 input 2 input 3 input 4 input 5 input 6 input 7

Which I was able to further reduce to 1.9038 sec with this solution:

import java.util.ArrayList;
import java.util.Scanner;
class TestClass {
    public static void main(String args[] ) throws Exception {
        Scanner keyboard=new Scanner(System.in);
        int t=keyboard.nextInt();
        keyboard.nextLine();
        ArrayList<String> vowelList= new ArrayList<>();
        vowelList.add("a");
        vowelList.add("e");
        vowelList.add("i");
        vowelList.add("o");
        vowelList.add("u");
        while(t!=0){
            String s= keyboard.nextLine();
            int len=s.length();
            String sub=s.substring(4,len-4);
            String[] splitted=sub.split("\\B");
            ArrayList<String> splt= new ArrayList<>();
            for(String x:splitted){
                splt.add(x);
            }
            splt.removeAll(vowelList);

            int size=splt.size();
            System.out.println(size+4+"/"+len);
            t--;
        }
    }
}

Now if I'm using List<String> vowelList= new ArrayList<>(); and List<String> splt= new ArrayList<>(); instead of the above two ArrayList declaration above, I'm further able to reduce it to 1.8892 sec.

What are more possible ways of optimizing the above code which can reduce the running time? And why is their time difference using Implemented ArrayList call and through interface call of List? Or has it just happened without any reasons?

Answer 1

So, performance. Let's list off things that are commonly done wrong that you do in your code:

1. print statements in a loop
2. line-by-line parsing of input
3. mid-list removals of values (removeAll())
4. not enough functions

The performance can be significantly improved by doing batch operations on the input, processing, and output.

Additionally, the last point is important. Java compiles code essentially on a method-by-method basis. By keeping all your code in the main method you are reducing the possibility for Java to compile and optimize it.

Read the whole file in, split the lines out in one operation, write all the results out as one string.

That will likely remove more than half your execution time... but your actual algorithm is slow as well.

Since you use regular expressions to split the characters, you may as well use one to just clean up the whole URL... and strip all vowels that way.

Here's a scratch-up of what I would consider given this task. It shows the ideas I was mentioning, and also uses some Java 8 features:

public static void main(String[] args) throws IOException {
    for (String infile : args) {
        System.out.println(processSource(Paths.get(infile)));
    }
}

private static String processSource(Path path) throws IOException {
    List<String> alldata = Files.readAllLines(path);
    Iterator<String> it = alldata.iterator();
    final int size = Integer.parseInt(it.next());

    String[] results = new String[size];
    for (int cnt = 0; it.hasNext() && cnt < size; cnt++) {
        results[cnt] = computeRatio(it.next());
    }

    return String.join("\n", results);

}

private static final Pattern DISCARD = Pattern.compile("(^www\\.)|[aeiou]");

private static final String computeRatio(String url) {
    int limit = url.lastIndexOf('.');
    String clean = DISCARD.matcher(url.substring(0, limit)).replaceAll("");
    // include the URL for debug:
    // return String.format("%d/%d -> %s", clean.length() + url.length() - limit, url.length(), url);

    // simple result
    return String.format("%d/%d", clean.length() + url.length() - limit, url.length());
}

Answer 2

The first place I would start with is how your read input and do output. Since IO operations are can be a bottleneck when it comes to competitive programming, it would be a good idea to start with these first.

A good way to reduce the bottleneck is to use BufferedStreams

In your case:

try(BufferedReader bf = new BufferedReader(new InputStreamReader(System.in))) {
    bf.readLine();
    // ignore the line
    for(String line = bf.readLine(); line != null; line = bf.readLine()) {
        // do something with each line
    }
} catch(IOException ioe){}