Algo 200 - A Substring

Writer: Jacob Edelman and Jakob Degen
Flag: 379

Analyzing the conditions for the flag reveal that because every sequence of A's is counted only once, we must only test for the beginning character of any sequence. The three conditions to do this for any character are fairly simple:

  1. The character must be an A: This is rather obvious, as a sequence of A's can only begin with an A.
  2. The character must be preceded by a character other than an A: This stems from the third of the original conditions, which dictates that the sequence be bounded by non-A characters, or in other words a non-A character has to precede our character.
  3. The final condition is that the character be followed by an A. This is because the sequence of A's must have a length of at least two characters, both of which must be A, and so the character immediately following the first character must be an A.

There is however one exception to this rule: The very first character in the string. If it is an A, then it only has to have an A following it, as the sub-string may begin with the file.

An implementation of this process can be seen in the following Java code:

public static int count(String s){
        int found = 0;

        for(int i = 0; i < s.length() - 1; i++){ //We skip the last character as it cannot be a valid first character of a sequence
            if(i == 0)
                if(s.charAt(i) == 'a' && s.charAt(i + 1) == 'a') 
                if(s.charAt(i - 1) != 'a' && s.charAt(i) == 'a' && s.charAt(i + 1) == 'a')

        return found;

results matching ""

    No results matching ""