CareerCup

void findCount_iter(const std::string& str, int currIndex, char currChar, int& count)
{
    if (str.size() == currIndex)
    {
        // Only if we have a valid string, increment the count
        if (currChar == 'c')
        {
            ++count;
        }
        
        return;
    }

    // Possibly including the current char
    if (str[currIndex] == currChar)
    {
        findCount_iter(str, currIndex + 1, currChar, count);
    }
    else if (str[currIndex] == currChar + 1)
    {
        findCount_iter(str, currIndex + 1, currChar + 1, count);
    }

    // Skipping the current char
    findCount_iter(str, currIndex + 1, currChar, count);
}

int findCount(const std::string& str)
{
    int count = 0;
    findCount_iter(str, 0, 'a' - 1, count);
    return count;
}

void findCount_iter(const std::string& str, int currIndex, char currChar, int& count)
{
    if (str.size() == currIndex)
    {
        // Only if we have a valid string, increment the count
        if (currChar == 'c')
        {
            ++count;
        }
        
        return;
    }

    // Possibly including the current char
    if (str[currIndex] == currChar)
    {
        findCount_iter(str, currIndex + 1, currChar, count);
    }
    else if (str[currIndex] == currChar + 1)
    {
        findCount_iter(str, currIndex + 1, currChar + 1, count);
    }

    // Skipping the current char
    findCount_iter(str, currIndex + 1, currChar, count);
}

int findCount(const std::string& str)
{
    int count = 0;
    findCount_iter(str, 0, 'a' - 1, count);
    return count;
}

public static int CountSequences(string input)
        {
            char[] chars = input.ToCharArray();
            int count = 0;
            CountSequences(chars, 0, 'a', ref count);
            return count;
        }
        //abcabc
        private static void CountSequences(char[] chars, int startIndex, char lookupChar, ref int count)
        {
            if (lookupChar > 'c') return;
            for (int currentIndex = startIndex; currentIndex < chars.Length; currentIndex++)
            {
                if (chars[currentIndex] == lookupChar) //found a match
                {
                    if (lookupChar == 'c')
                    {
                        count++;
                    }
                    else
                    {
                        CountSequences(chars, currentIndex + 1, (char)(lookupChar + 1), ref count);
                    }
                    CountSequences(chars, currentIndex + 1, lookupChar, ref count);
                }
            }
        }

The O(n) idea is to use dynamic programming. If letter is 'a' and you know the number of valid strings ending in 'a' for characters up to position i, the new number is 2n+1 because you keep all strings up to position i (n), you add this 'a' to all previous strings (+n) and you can have this char as a separate string (+1).
With a similar thinking
nBs = 2 nBs + nAs
nCs = 2 nCs + nBs

E.g.
a b c a b c
1 1 1 3 3 3 nAs
0 1 1 1 5 5 nBs
0 0 1 1 1 7 nCs

This problem can be done by recursive or iterative way.
Recursive way is very inefficient as it can be of the order of O(n2) plus a lot of method stacks gets created.

Iterative solution is best solution that gets over in O(n) times. Its given as below.
Its some one wants to know more about how its calculated then he can email me at teji.catia@gmail.com:

public class IterativeSeq {
	public static void main(String[] args){
		IterativeSeq t= new IterativeSeq();
		System.out.println("output="+t.CountSeq("abcabcaabbcc"));
	}	
	public static int CountSeq(String input){	
		int acount=0, bcount=0, ccount=0;
		char[] chars = input.toCharArray();
		for(int i=chars.length-1; i>=0;i--){
			if(chars[i]=='c'){
				ccount++;
			}else if(chars[i]=='b'){
        		bcount=((int)Math.pow(2,ccount)-1)+(bcount*2);   		
        	}else if(chars[i]=='a'){
        		acount=bcount+(2*acount);
        	}
		}
		return acount;
	}

}

This problem can be resolved in either recursive or iterative way.
Recursive way is very inefficient as it may take O(n^2) or more and causes many method stacks being built upon.
Iterative solution is best with guaranteed O(n) running time. Its a below.
If someone wants to know about how formula is derived. He can mail me at teji.catia@gmail.com.

public class IterativeSeq {
	public static void main(String[] args){
		IterativeSeq t= new IterativeSeq();
		System.out.println("output="+t.CountSeq("abcabcaabbcc"));
	}	
	public static int CountSeq(String input){	
		int acount=0, bcount=0, ccount=0;
		char[] chars = input.toCharArray();
		for(int i=chars.length-1; i>=0;i--){
			if(chars[i]=='c'){
				ccount++;
			}else if(chars[i]=='b'){
        		bcount=((int)Math.pow(2,ccount)-1)+(bcount*2);   		
        	}else if(chars[i]=='a'){
        		acount=bcount+(2*acount);
        	}
		}
		return acount;
	}

}

There can be more answer to the provided example so output should be more than 7.
i.e. {1,4,5,3,6};{1,4,2,3,6};{1,4,2,3,6};{1,5,3}; etc according to the question. let me know i am wrong.