def solution(n, inputText): numConsonants = 0 numWords = 0 numWordsThatHaventEnded = 0 length = 0
for character c in inputText: numConsonants = (c is consonant) ? (numConsonants + 1) : 0 length = length + 1 numWordsThatHaventEnded = (numConsonants >= n) ? (length - (n - 1)) : numWordsThatHaventEnded numWords += numWordsThatHaventEnded return numWords Sent from my iPad On 13 May 2013, at 14:36, Angel Java Lopez <[email protected]> wrote: > Yes, it is O(N) > > Hmmm... take into account you cannot take ALL starting points before the new > group of consonants you found. It should be limited by the previous group of > consonant found, so you don't count twice the occurrence. In that way, you > are adding the count of substrings that contains your new group of consonants > as THE FIRST WITH n consontants IN the substring we are counting. > > We don't need big state, a for with two or three state variables are enough > > And, of course, an string containing all the text in process > > Am I right? > > Angel "Java" Lopez > @ajlopez > > > On Mon, May 13, 2013 at 9:50 AM, Joseph DeVincentis <[email protected]> wrote: >> 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. > > -- > 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.
