This problem (1C A Consonants) can be solved in O(N). Proceed through the string character by character, keeping a counter indicating the number of consecutive consonants. When it reaches n, do the following: 1. Compute the number of substrings that contain this group of n consonants by multiplying the number of starting points before the group with the number of ending points after the substring. (Note that if there are k characters before the n consonants, there are k+1 starting points since you can include 0, 1, ..., k of them.) 2. Discard all of the string up to and including the first consonant of the group, and set the number of consecutive consonants to n-1. You've already counted all substrings containing that group of consonants, so this ensures you will never count any of them again.
You will of course need to use variables large enough to hold the largest possible answer, a string of maximum length containing only consonants with n=1, where every substring is counted. That's N(N+1)/2 if N is the number of characters. On Mon, May 13, 2013 at 7:03 AM, Vaibhav Tulsyan <[email protected]>wrote: > I solved the problem in Java. > My logic to solve the 'Consonants' problem is as follows: > 1. Find all possible substrings from the name of length 'n' or greater > (using substring( ) function) > 2. In each substring, check if 'n' consonants appear consecutively. > > > > This is an O(N^4) solution. For names of length (10^6), I thought I'd > use 'long' instead of 'int', but the substring( ) function works only > for integers. What should I do in order to resolve this, if I intend > to use the same logic? (Or should I change the logic) > -- > Regards, > Vaibhav Tulsyan. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
