Consonants Solution: Google codejam 2013 Round 1C

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the first problem from Online Round 1C 2013, top 1000 from this round will be eligible for next online round.

Problem Statement

In English, there are 26 letters that are either vowels or consonants. In this problem, we consider a, e, i, o, and u to be vowels, and the other 21 letters to be consonants.

A tribe living in the Greatest Colorful Jungle has a tradition of naming their members using English letters. But it is not easy to come up with a good name for a new member because it reflects the member’s social status within the tribe. It is believed that the less common the name he or she is given, the more socially privileged he or she is.

The leader of the tribe is a professional linguist. He notices that hard-to-pronounce names are uncommon, and the reason is that they have too many consecutive consonants. Therefore, he announces that the social status of a member in the tribe is determined by its n-value, which is the number of substrings with at least n consecutive consonants in the name. For example, when n = 3, the name “quartz” has the n-value of 4 because the substrings quartz, uartz, artz, and rtz have at least 3 consecutive consonants each. A greater n-value means a greater social status in the tribe. Two substrings are considered different if they begin or end at a different point (even if they consist of the same letters), for instance “tsetse” contains 11 substrings with two consecutive consonants, even though some of them (like “tsetse” and “tsetse“) contain the same letters.

All members in the tribe must have their names and n given by the leader. Although the leader is a linguist and able to ensure that the given names are meaningful, he is not good at calculating the n-values. Please help the leader determine the n-value of each name. Note that different names may have different values of n associated with them.

Input

The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case gives the name of a member as a string of length L, and an integern. Each name consists of one or more lower-case English letters.

Output

For each test case, output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is the n-value of the member’s name.

Limits

1 ≤ T ≤ 100.
0 < n ≤ L.

Small dataset

1 ≤ L ≤ 100.

Large dataset

1 ≤ L ≤ 10⁶.
The input file will be no larger than 6MB.

Sample

Consonants problem Google codejam Online Round 1C 2013 solution with explanation

In the problem, for a given name and number n, we have to find the number of substrings with at least n consecutive consonants.
We can check if there are n consecutive consonants available in the input string anywhere, then we can count the number of possible strings we can form using these consecutive consonants. Let say there are k letters before this string and m letters after these consecutive strings then we can say we can form (k+1)*(m+1)(by taking 0 or more letters from any side) sub strings which has at least n consecutive consonants.
Now if we do this for every n consecutive consonants we will count few strings more than once, to discount them we will change our k (starting point of the sub string) if a starting point of sub string is already counted we will not count it again so if x letters are counted earlier then our k will become k – x;

Here is the Java code for Consonants problem in Google codejam Online Round 1C 2013

package googlecodejam2013;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.Reader;
import java.math.BigInteger;

public class NValue {

	public static String getNValue(String input, int n){
		BigInteger count = new BigInteger("0");

		int len = input.length();
		int previouslyCounted = -1;
		int numberOfConsecutiveConsonants = 0;
		for(int i =0; i < len; i++){
			if(isConsonant(input.charAt(i))){
				numberOfConsecutiveConsonants++;
			}else{
				numberOfConsecutiveConsonants = 0;
			}
			if(numberOfConsecutiveConsonants >= n){
	        	int k = (i + 1) -n + 1;//additional 1 for no letter
	        	if(previouslyCounted != -1){
	        		k -= previouslyCounted;
	        	}
	        	previouslyCounted = (i + 1) -n + 1;
	        	BigInteger c = new BigInteger(""+(k)).multiply(new BigInteger(""+(len-i)));// m = len-i
	        	count = count.add(c);
	        }
		}
		return count.toString()+"";
	}

	static boolean isConsonant(char c) {
		return c != 'a' && c != 'e' && c != 'i' && c != 'o' && c != 'u';
	}

	public static void main(String[] argv) {
		try {
			long startTime = System.currentTimeMillis();
			Reader reader = new FileReader("C:\\Users\\XYZ\\Desktop\\google\\nval\\sample.in");
			BufferedReader bufReader = new BufferedReader(reader);
			String x = bufReader.readLine();
			int numOfTestCases = Integer.parseInt(x);
			int count = 0;

			File file = new File("C:\\Users\\XYZ\\Desktop\\google\\nval\\sample.out");
			FileWriter writer = new FileWriter(file);
			for(count =1; count<= numOfTestCases; count++) {
				String input = bufReader.readLine();
				String output = getNValue(input.split(" ")[0], Integer.parseInt(input.split(" ")[1]))+"";
				writer.write("Case #" + count + ": " + output+"\n");
				System.out.println("Case #" + count + ": " + output);
			}
			writer.close();
			System.out.println("Total time = " + (System.currentTimeMillis() - startTime));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Facebook Comments