CareerCup

f1(n) is the number of strings with the last two char same;
f2(n) is the number of strings with the last two char different;
f1(n)=f1(n-1)+f2(n-1);
f2(n)=2*f1(n-1)+f2(n-1);
f1(2)=3;
f2(2)=6;

f1(n) is the number of strings with the last two char same;
f2(n) is the number of strings with the last two char different;
f1(n)=f1(n-1)+f2(n-1);------------------1
f2(n)=2*f1(n-1)+f2(n-1);----------------2
f1(2)=3;
f2(2)=6;


Now,
f(n)=f1(n)+f2(n)
=>f(n-1)=f1(n-1)+f2(n-1)=f1(n)=========from 1------------3

=>f(n)=f(n-1)+f2(n)
=>f(n)=f(n-1)+2*f1(n-1)+f2(n-1)=======from 2
=>f(n)=f(n-1)+(f1(n-1)+f2(n-1))+f1(n-1)
=>f(n)=f(n-1)+f(n-1)+f1(n-1)
=>f(n)=f(n-1)+f(n-1)+f(n-2)
=>f(n=)2*f(n-1)+f(n-2)

Also,
f(2)=f1(2)+f2(2)=3+6=9
f(1)=f1(2)=3

This final solution is f(n)=2*f(n-1)+f(n-2), f(1)=3, f(2)=9

I think the problem can be solved using RabinKarp Algorithm,
Here is the code.
Please tell me if I have done any error.

package com.algorithm.string.pattern.search;

import java.util.Arrays;

public class RabinKarpApplication {

	public int hashValue(String input, int start, int end) {
		int temp = 0;
		char[] inputarr = input.toCharArray();
		for (int i = 0; i < end; i++) {
			temp += inputarr[i];
		}
		return temp;
	}

	boolean checkEquality(char[] source, char[] desti){
		Arrays.sort(source);
		Arrays.sort(desti);
		for(int i=0 ;i< source.length;i++){
			if(source[i] != desti[i]){
				return false;
			}
		}
		return true;
	}

	public boolean matchPattern(String source, String pattern) {
		int patternHashValue = hashValue(pattern, 0, pattern.length());
		int sourceHashValue = hashValue(source, 0, pattern.length());
		if (sourceHashValue == patternHashValue) {
			if(checkEquality(source.substring(0, pattern.length()).toCharArray(), pattern.toCharArray())){
				return true;
			}
		}

		char[] sourcearray = source.toCharArray();
		for (int i = pattern.length() ; i < sourcearray.length; i++) {
			sourceHashValue = sourceHashValue -  sourcearray[i - pattern.length()] + sourcearray[i];
			if(sourceHashValue == patternHashValue){
				if(checkEquality(source.substring(i-pattern.length()+1, i+1).toCharArray(), pattern.toCharArray())){
					return true;
				}
			}
		}

		return false;
	}

	public static void main(String[] args) {
		RabinKarpApplication rkapps = new RabinKarpApplication();
		String source = "bcabbcde";
		String pattern = "abc";
		if(rkapps.matchPattern(source, pattern)){
			System.out.println("Invalid");
		}else{
			System.out.println("Valid");
		}
	}
}

We can use Dynamic Programming , Let define T[n,'ab'] be the number of valid strings of length n which starts with 'ab', in the same way we can define T[n,'bc'], T[n,'aa'], T[n,'ba'] .... Then T[n,'ab'] = T[n-2,'bc]+T[n-2,'ba']+T[n-2,'bb]+T[n-2,'aa']+T[n-2,'ac']+T[n,'ab']
in the same way we can calculate for the rest for n = 2 and n=3 which are the base cases we can calculate them easily, The running time would be O(n) and the storage space is O(n) too

The question asks to "output the amount of all possible strings", so I haven't quite answered that below; rather, I've outputted all possible strings. I believe this solution is essentially what HoneyBall was describing.

def emitStrings(stringSoFar, N, strings) :
	length = len(stringSoFar)
	if length is N : return

	validChars = ['a','b','c']

	if length >= 2 :
		# To figure out whether we have consecutive characters, we try
		# removing the last two characters from a copy of validChars. If we
		# were able to remove 'char2', then we have a combination like "ab",
		# and we must remove "c" from validChars.
		validChars2 = validChars[:]
		char1 = stringSoFar[length - 1]
		char2 = stringSoFar[length - 2]

		validChars2.remove(char1)
		if char2 in validChars2 :
			validChars2.remove(char2)

			# There's only one left now.
			validChars.remove(validChars2[0])

	for char in validChars :
		if length is N - 1 :
			strings.append(stringSoFar + char)
		emitStrings(stringSoFar + char, N, strings)

def main():
	strings = []
	emitStrings('', 8, strings)
	print strings

if __name__ == '__main__':
	main()

Output:

['aaaaa', 'aaaab', 'aaaac', 'aaaba', 'aaabb', 'aaaca', 'aaacc', 'aabaa', 'aabab', 'aabba', 'aabbb', 'aabbc', 'aacaa', 'aacac', 'aacca', 'aaccb', 'aaccc', 'abaaa', 'abaab', 'abaac', 'ababa', 'ababb', 'abbaa', 'abbab', 'abbba', 'abbbb', 'abbbc', 'abbcb', 'abbcc', 'acaaa', 'acaab', 'acaac', 'acaca', 'acacc', 'accaa', 'accac', 'accbb', 'accbc', 'accca', 'acccb', 'acccc', 'baaaa', 'baaab', 'baaac', 'baaba', 'baabb', 'baaca', 'baacc', 'babaa', 'babab', 'babba', 'babbb', 'babbc', 'bbaaa', 'bbaab', 'bbaac', 'bbaba', 'bbabb', 'bbbaa', 'bbbab', 'bbbba', 'bbbbb', 'bbbbc', 'bbbcb', 'bbbcc', 'bbcbb', 'bbcbc', 'bbcca', 'bbccb', 'bbccc', 'bcbba', 'bcbbb', 'bcbbc', 'bcbcb', 'bcbcc', 'bccaa', 'bccac', 'bccbb', 'bccbc', 'bccca', 'bcccb', 'bcccc', 'caaaa', 'caaab', 'caaac', 'caaba', 'caabb', 'caaca', 'caacc', 'cacaa', 'cacac', 'cacca', 'caccb', 'caccc', 'cbbaa', 'cbbab', 'cbbba', 'cbbbb', 'cbbbc', 'cbbcb', 'cbbcc', 'cbcbb', 'cbcbc', 'cbcca', 'cbccb', 'cbccc', 'ccaaa', 'ccaab', 'ccaac', 'ccaca', 'ccacc', 'ccbba', 'ccbbb', 'ccbbc', 'ccbcb', 'ccbcc', 'cccaa', 'cccac', 'cccbb', 'cccbc', 'cccca', 'ccccb', 'ccccc']

As there are N spaces available and we have 3 unique things to choose from so to print all different combinations we have only one choice 3*3*3*3*3 (no of iterations)
But we got no other choice.
However if we don't want sequence then we can simply ignore the cases in which we get a sequence.

Here is the code:

void allPossibleStrings(char *a, char *b, int len, int n, int k)
{
	int i=0, j=0;

	for(i=0; i<len; i++)
	{
		if(k < n)
		{
			b[k] = a[i];
			if(k >= len-1)
			{
				if(hasAllElements(b+k-len+1, len))
				{					
					continue;		
				}
			}
			allPossibleStrings(a,b,len,n,k+1);
		}
		else
		{
			printf("\n");
			for(j=0; j<n; j++)
			{
				printf("%c,",b[j]);
			}
			break;
		}
	}
}

The function hasAllElements() will check if b has all the elements that are in array a (which basically checks all kinds of sequence).
This code i have written is a general form.

Considering that all the generated permutations of length N can have repeated characters then here is a simple solution written in Ruby:

def non_repeat_permutation(str)

  #min number of characters that should not get repeated e.g: min len {"ab", "abc", "abbca"...}
  min_repeat = 2

  # number of unique characters in the string e.g: {str = "aerfdcse"}, uniq_char_length = 7
  uniq_char_len = str.split("").uniq.length

  # number of unique characters that should not be present next to each other e.g: len {a ,b ,c}
  uniq_repeat_char_len = 3

  repeat_str_permutations = (uniq_repeat_char_len ** min_repeat) * (uniq_char_len ** (str.length - min_repeat))

  total_permutations = (uniq_char_len ** str.length)

  non_repeat_permutations = total_permutations - repeat_str_permutations
  puts non_repeat_permutations

end

non_repeat_permutation ARGV[0]

f(0)=0
f(1)=3
f(2)=9
f(n) = f(n-1) + 2*f(n-2) + 2*f(n-3) + ... + 2*f(4) + 24

public static void findSolutions(String word, int n) {
char[] letters = word.toCharArray();
int sum = getSum(letters);
findSolutions(letters, n, "", sum);
}


private static void findSolutions(char[] letters, int n, String result, int sum) {
if (result.length() > 2 && getSum(result.substring(result.length() - 3, result.length()).toCharArray()) == sum) {
return;
}
if (result.length() == n) {
System.out.println(result);
} else {
for (int i = 0; i < letters.length; i++) {
findSolutions(letters, n, result + letters[i], sum);
}
}
}

private static int getSum(char[] lookUp) {
int sum = 0;
for (int i = 0; i < lookUp.length; i++) {
sum += lookUp[i];
}
return sum;
}

We can use backtracking:

public static void findSolutions(String word, int n) {
		char[] letters = word.toCharArray();
		int sum = getSum(letters);
		findSolutions(letters, n, "", sum);
	}


	private static void findSolutions(char[] letters, int n, String result, int sum) {
		if (result.length() > 2 && getSum(result.substring(result.length() - 3, result.length()).toCharArray()) == sum) {
			return;
		}
		if (result.length() == n) {
			System.out.println(result);
		} else {
			for (int i = 0; i < letters.length; i++) {
					findSolutions(letters, n, result + letters[i], sum);
			}
		}
	}
	
	private static int getSum(char[] lookUp) {
		int sum = 0;
		for (int i = 0; i < lookUp.length; i++) {
			sum += lookUp[i];
		}
		return sum;
	}

Recursive solution. If the last two characters are distinct we should use only them as the next character.

public static void print(int n) {
    print(n, "");
}

private static void print(int n, String s) {
    if (n == s.length()) {
        System.out.println();
        return;
    }
    
    Set<Character> validChars = new HashSet<>();
    //if last two characters are distinct, we should use only them as the next character
    if (s.length() > 1 && s.charAt(s.length() - 1) != s.charAt(s.length() - 2)) {
        validChars.add(s.charAt(s.length() - 1));
        validChars.add(s.charAt(s.length() - 2));
    } else {
        validChars.add('a');
        validChars.add('b');
        validChars.add('c');
    }
    
    for (Character c : chars) {
        print(n, s + c);
    }
}

Let a=0, b=1 and c=2. Let counts[m][i][j] be the number of valid strings with length m+1, and the last 2 characters being what i & j would correspond to. For instance, counts[1][0][2] would be the number of valid strings with length 2, where the last 2 characters are "a" and "c". In this case, there's only 1 such string so counts[1][0][2] would be 1. We can then use dynamic programming to fill up this multi-dimensional array to compute the number of valid strings of length N.

Below is my Java code for doing so. Note that it can be improved in at least 2 ways:
(1) Leverage the symmetry so instead of computing for all "a", "b" and "c", we only compute one of them and multiply result by 3.
(2) After calculating the new values for each iteration "m", we don't need all the old values at iteration "m-1" anymore. So we can reuse that array.

class ABC {
	static int combinations(int n) {
		if(n <= 2)
			return (int)Math.pow(3, n);
		int counts[][][] = new int[n][3][3];
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				counts[1][i][j] = 1;
			}
		}

		for(int m=2; m<n; m++) {
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					for(int k=0; k<3; k++) {
						if(compatible(i,j,k))
							counts[m][j][k] += counts[m-1][i][j];
					}
				}
			}
		}

		int total = 0;
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				total += counts[n-1][i][j];
			}
		}
		return total;
	}

	static boolean compatible(int i, int j, int k) {
		int sum = i + j + k;
		return(sum != 3 || i == j || j == k || k == i);
	}

	public static void main(String[] args) {
		System.out.println(combinations(Integer.parseInt(args[0])));
	}
}

public static boolean check (String s) {
char ch[]=s.toCharArray();
boolean flag = true;
int clen= ch.length;
if (clen<3) { flag=false; }
// System.out.println("String length is " + clen);
for (int i=0;i<clen-2;i++)
{if (ch[i]!=ch[i+1] && ch[i]!=ch[i+2] && ch[i+1]!=ch[i+2])
{ return false; }
}
return true;
}


///is this code right?

This question asks "the amount of", so the answer should be some value.
In here, I would like to show O(N) answer.

Let's define functions A,B and C

A(N) is the amount of all possible cases a string is consists of a, b, and c with length N
B(N) is the amount of all possbile cases a string is consists of a, b, and c with length N have consecutive a,b,c
C(N) is the amount of all possible strings of length N that don't of have consecutive a,b,c

A(N) = 3^N
B(N) = C(N-2) * Combination(N, 3)
= C(N-2) * (N ) * (N - 1)* (N - 2) / 3 * 2* 1

C(0) = 1
C(1) = 1
C(2) = 1
C(N) = A(N) - B(N)

We can caclurate C using DP.

long calcAmount(int N){
	assert N > 2;
	long[] dp = new long[N+1]; // 1 indexed
	dp[0] = 1;
	dp[1] = 1;
dp[2] = 1;
	for(long i = 3; i <= N; i++){
		dp[i] = (long) Math.pow(i, 3) - dp[i - 2] * i * (i - 1) * (i - 2) / 6L; 
}
return dp[N];
}

public static void main(String[] args) {
char[] chars= {'a', 'b', 'c'};
int N = 5;
char[] ret = new char[N];
print(ret, chars, N, 0);
}

private static void print(char[] ret, char[] chars, int size, int idx) {
if (size == 0) {
for (int i = 0; i < ret.length; ++i)
System.out.print(ret[i]);
System.out.println();
return;
}

for (int i = 0; i < size; ++i) {
for (int j = 0; j < chars.length; ++j) {
ret[idx] = chars[j];
if (idx >= 2) {
Map<Character, Boolean> map = new HashMap<Character, Boolean>();
for (int k = idx - 2; k <= idx ; ++k) {
map.put(ret[k], true);
}
if (map.size() == chars.length) {
continue;
}
}
print(ret, chars, size - 1, idx + 1);
}
}
}

First consider only the strings that begin with 'a'. We can build a tree with the number of valid strings (beginning with 'a') equal to the number of leaves in the tree. Start a tree with root 'a' and to this we can add 3 children 'a', 'b' and 'c'. To the child node 'a', we can attach children 'a','b' and 'c'. However, to the 'b' and 'c' children we can only attach 2 children. Continuing, this looks something like:

n = length of string;
S(n) = number of valid strings beginning with 'a';
a 									n=1, S(1) = 1
a | b | c 								n=2, S(2) = 3
a b c | a b | a c 						n=3, S(3) = 7
a b c | a b | a c | a b | a b c | a c | a b c		n=4, S(4) = 15
...									n=N, S(N) = 2*S(N-1)+1

The separators divide the child nodes amongst the parent notes. Namely, the number of groupings of nodes at depth n+1 should equal the number of nodes at height n. Note that we could create similar trees with roots 'b' and 'c' and the valid strings in each tree will be distinct (since they begin with different letters!). Therefore, the total number of valid strings of length N, call this T(N), is given by T(N)=3*S(N) which can be computed recursively.

Also note that this formula only computes the number of valid strings. To list the strings themselves simply store the trees. In fact, you only need to store the tree corresponding to 'a' and write a small algorithm that relabels the nodes appropriately.

This is more of a mathematical problem than a programming one.

The general formula for the solution to this problem:
N= String length
x=number of unique letters

#valid Strings = x^N - (N-x)*(N-x+1)*x!

#define HAS_A 1
#define HAS_B 2
#define HAS_C 4

#define HAS_NONE 0
#define HAS_ALL  (HAS_A | HAS_B | HAS_C )

#define CHAR2BIT(c) ((c) == 'a' ? HAS_A : ((c) == 'b' ? HAS_B : HAS_C))

static void
print_non_consec (int len, char *buf, char *ptr)
{
    char prev = HAS_NONE;
    char ch = 0;

    // check for illegal values (len 0, buf > ptr)
    assert(len);
    assert(buf <= ptr);
    // get the previous char and the previous-previous one
    // the order does not matter, so keep it in a bitmap
    if (ptr - buf >= 1) {
        prev |= CHAR2BIT(*(ptr-1));
    }
    if (ptr - buf >= 2) {
        prev |= CHAR2BIT(*(ptr-2));
    }
    // try add each char and check for non-consecutive requirement
    for (ch = 'a'; ch <= 'c'; ch++) {
        if ( (prev | CHAR2BIT(ch)) != HAS_ALL) {
        // if allowed, build the rest of the word recursively
            *ptr = ch;
            if (len > 1) {
                print_non_consec(len-1, buf, ptr+1);
        }    else { 
        // if reached the word end, print it
                *(ptr+1) = '\0';
                printf("%s\n",buf);
            }
        }
    }
}

Here is an O(N) solution for finding the *count* of acceptable strings. It calculates the count for strings of length up to N. It uses O(N) space, but it is trivial to bring the space to O(1). The way it is below, you can make lookups to countsameA and countdiffA vectors for different values of N.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    int N=50;
    vector<long> countsameA(N), countdiffA(N);

    // initialize the count vector for two same chars and two different chars
    countsameA[0] = 1;
    countdiffA[0] = 1;
    for (int i = 1; i<N; ++i){
        countsameA[i] = countsameA[i-1] + 2*countdiffA[i-1];
        countdiffA[i] = countsameA[i-1] + countdiffA[i-1];
    }
    
        long total = 3*countsameA[N-2] + 6*countdiffA[N-2];
        cout << N << " " << total << endl;
    
    return 0;
}

Generating all strings obeying the rule would require exponential complexity -- either via recursion or dynamic programming.

A recursion works but when you are adding the next character, you have to check for the "constraints". In this case, making sure that the last two character of the sequence are either equal or at least one of them equal to the new character you are adding.

public class AllStrings {    
        
    public static void PrintAll(int length) {        
        char_arr = new char[length];
        pos = 0;
        PrintSeq();
    }
    
    private static void PrintSeq() {
        if (pos == char_arr.length) {
            for (int i = 0; i < char_arr.length; i++)
                System.out.print(char_arr[i]);
            System.out.println();                        
        }
        else {
            if (IsValid('a')) {
                char_arr[pos++] = 'a';
                PrintSeq();
                pos--;
            }
            if (IsValid('b')) {
            char_arr[pos++] = 'b';
            PrintSeq();
            pos--;
            }
            if (IsValid('c')) {
                char_arr[pos++] = 'c';
                PrintSeq();
                pos--;
            }            
        }        
    }
    private static boolean IsValid(char a) {
        if (pos < 2)
            return true;
        else
            return !((a != char_arr[pos - 1]) && (a != char_arr[pos - 2]) && (char_arr[pos - 1] != char_arr[pos - 2]));
    }


    private static char[] char_arr;
    private static int pos = 0;
}

a simple resursion will solve this

char str[1000];
int n;

void solve(int s , int n) {
	if(n==s) {
		str[s] = 0;
		printf("%s\n", str);
		return;
	}
	
	FOR(i,0,2) {
		if(s<=1) {
			str[s] = 'a' + i;
			solve(s+1,n);
		}
		else if('a'+i == str[s-1] || 'a'+i == str[s-2]){
			str[s] = 'a' + i;
			solve(s+1,n);		
		}
	}
}

int main() {
	scanf("%d", &n);
	solve(0,n);
	return 0;
}

This seems like it is just a simple math question... I may be wrong but I think the way to solve this is to think of it like this:

If you had a string of abc without any constraints you would have 3^N possible strings
now with the constraints:
You have 3 options for the first spot in the string(abc), and then for each of the remaining slots(N-1) you have 2 options(the two letters you didn't use for the previous spot), so the formula should be 3*2^(N-1)

i think the correct formula will be
f(n)=2*f(n-1)+f(n-2)
f(1)=3
f(2)=6
here is the source code for displaying all strings

#include<stdio.h>
#include<stdlib.h>
void printString(char *str,int index,int n)
{
 if(index==n)
 {

  printf("\n %s",str);
   return;
  }
 if(index<2)
 {
  str[index]='a';
  printString(str,index+1,n);
 str[index]='b';
  printString(str,index+1,n);
 str[index]='c';
  printString(str,index+1,n);
}
else
{
 if(str[index-2]!=str[index-1])
 {
   str[index]=str[index-1];
   printString(str,index+1,n);
  str[index]=str[index-2];
   printString(str,index+1,n);
 }

else  
 {
   str[index]='c';
   printString(str,index+1,n);
  str[index]='b';
   printString(str,index+1,n);
 str[index]='a';
   printString(str,index+1,n);
 }

}

 


}
int main()
{
char str[50]={'\0'};
printString(str,0,2);

}

void GenerateNonConsecutiveABC(int N, std::string &S,int State)
{
    static char ABC[3] = {'a','b','c'};
    static int SM[11][3] = 
    {
        {1,2,3}, //empty
        {1,4,5}, //a
        {6,2,7}, //b
        {8,9,3}, //c
        {6,2,10}, //ab
        {8,10,3}, //ac
        {1,4,10}, //ba
        {10,9,3}, //bc
        {1,10,5}, //ca
        {10,2,7}, //cb
        {10,10,10} //garbage
    };

    if(S.size() == N)
    {
        cout << S.c_str() << endl;
    }
    else
    {
        for(int i = 0; i < 3; i++)
        {
            if(SM[State][i] != 10)
            {
                S.push_back(ABC[i]);
                GenerateNonConsecutiveABC(N,S,SM[State][i]);
                S.pop_back();
            }
        }
    }
}

// This is javascript

function out1(w,x) {
	var z= {
		'aa' : 'a',
		'ab' : 'a',
		'ac' : 'a',
		'ba' : 'a',
		'bb' : 'a',
		'bc' : 'b',
		'ca' : 'a',
		'cb' : 'b',
		'cc' : 'a'
	}[w+x];

	return z;
}

function out2(w,x) {
	var z = {
		'aa' : 'c',
		'ab' : 'b',
		'ac' : 'c',
		'ba' : 'b',
		'bb' : 'c',
		'bc' : 'c',
		'ca' : 'c',
		'cb' : 'c',
		'cc' : 'c'
	}[w+x];

	return z;
}

function out3(w,x) {
	var z = {
		'aa' : 'b',
		'ab' : '',
		'ac' : '',
		'ba' : '',
		'bb' : 'b',
		'bc' : '',
		'ca' : '',
		'cb' : '',
		'cc' : 'b'
	}[w+x];

	return z;
}

function gen4( n, p1, p2, str ) {
	if ( n == 0 ) {
		gs.print(str);
	}
	else {
		var x = out1(p1, p2);
		var y = out2(p1, p2);
		var z = out3(p1, p2);

		gen4( n-1, p2, x, str + x);
		gen4( n-1, p2, y, str + y);

		if ( z ) {
			gen4( n-1, p2, z, str + z);
		}
	}
}

function gen3( n, p1, str ) {
	gen4( n-1, p1, 'a', str + 'a');
	gen4( n-1, p1, 'b', str + 'b');
	gen4( n-1, p1, 'c', str + 'c');
}

function gen1( n ) {
	gen3( n-1, 'a', 'a' );
	gen3( n-1, 'b', 'b' );
	gen3( n-1, 'c', 'c' );
}

gen1( 5 );

Total Number of Strings possible: n1= 3^N
Strings With consecutive a,b& c : n2== 3^(N-3)* (3)! * (N-2)!
Strings without consecutive a,b& c : n3= n1-n2

static void FindStrings(String result, String str, int size) {
if (result.length() >= size) {
System.out.println(result);
}
else {
for (int i = 0; i < str.length(); i++) {
int nlen = result.length();

if (nlen >= 2)
{
if ((result.charAt(nlen - 1)+"").equals(str.charAt(i)+"") ||
(result.charAt(nlen - 2)+"").equals(str.charAt(i)+"") ||
(result.charAt(nlen - 1)+"").equals(result.charAt(nlen - 2)+""))
FindStrings(result + str.charAt(i), str, size);
}
else
FindStrings(result + str.charAt(i), str, size);
}
}
}

My code below does not have extensibility. When there are four kinds of distinct letters in str, it doesn't work.
public static int count( String s, int n ) {
int res = 0;
int start = 0;
Set<Character> past = new HashSet<Character>();
char prev = ' ';
char[] chars = s.toCharArray();
int i = 0;
for( ; i < chars.length; i++ ) {
char c = chars[i];
if( past.contains(c) && c == prev ) {
past.clear();
past.add( c );
} else if( !past.contains( c ) ){
past.add( c );
if( past.size() == 3 ) {
past.clear();
past.add( prev );
past.add( c );
if( i - n >= start )
res += ( i-n-start+1 );
start = i - 1;
}
}
prev = c;
}
res += ( i - n >= start ) ? ( i - n - start + 1 ) : 0;
return res;
}

If N is odd, ans = 3 * 7 ^ ((n-1)/2);

If N is even, ans = 51 * 7 ((n-4)/2);

i am thinking of generating all the strings of length N means generating all the string of length N by putting a ,b,c at various place of string and then when string size becomes N then check if it contains a,b,c consecutive or not.........
if not then print it