• 3

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

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;

Comment hidden because of low score. Click to expand.
0

This is correct I think - I came to exactly the same solution. The remaining question is, if we can with a bit of magic make a nonrekurent formula a compute it in constatn time :-)

Comment hidden because of low score. Click to expand.
1
of 1 vote

O(log n) (arithmetic operations) can be done (view as matrix multiplication).

O(1)? unlikely, as the result would be exponential (have to compute x^n).

Comment hidden because of low score. Click to expand.
0

Its simple 3^n - 6×(n-2)!

Comment hidden because of low score. Click to expand.
0

@yo yo honey singh: Can you please explain how you got that formula?

Comment hidden because of low score. Click to expand.
0

Sure. If f1 and f2 are defined as above. f1(n) can be derived from string of length n-1, with last two char the same and not the same. For the last two char the same for n-1 length string, if the resulted last two char are the same, that constrains the last char of n length to be only one option. For string of length n-1, with last two char different, the resulting n length string with the last two char the same also constrains the last char of n length to be only one option. Therefore, f1(n)=f1(n-1)+f2(n-1).

Similarly, f2(n)=2*f1(n-1)+f2(n-1), since if we start from n-1 length string with last two char the same, we can have two options for the last char of n length string. If we start from n-1 length string with last two char different, we only have one option for the last char of n length string.

Comment hidden because of low score. Click to expand.
0

@yo yo honey singh: your formula does not work for n=4. I think the right one is: 3^n - [3^(n - 3)] * (n - 2) * 3!

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}
}``````

Comment hidden because of low score. Click to expand.
0

is your hash function valid for Rabin-Karp algorithm?

By the way problem is different, you are given Alphabet A={a,b,c}, generate a sequence of strings in which characters a, b and c are not adjacent to each other

Comment hidden because of low score. Click to expand.
0

I think you need to output number of possible solutions.

Comment hidden because of low score. Click to expand.
0

wht abt checking whether abc#bac#cab#cba#acb#bca and generated string have a common substring ..if not then valid otherwise invalid..

Comment hidden because of low score. Click to expand.
0

i mean substring of length 3.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

This looks right, if the question it to count the total number (and it seems to be that, other folks seem to have misread).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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']``

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

The function can be called like this:

``````char a[] = {'a','b','c'};
char b[N];

allPossibleStrings(a, b, 3, N, 0);
return 0;``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

You got it almost right, the problem needs no programming. A simple counting can do.

3^5 - 3*3! = 225 is the answer.
3^5 for all the possible combinations of a,b & c in a 5-letter string.
3 is for the possible number of consecutive locations for 3 elements. (1,2,3) (2,3,4) and (3,4,5) are the 3 possibilities for consecutive locations of 3 elements in 5 places.
3! is the for the permutation of (a,b,c) in the 3 consecutive locations identified above.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@Erasmus. It is not 225. for n = 3 it is 123. The formula doesn't seem to be right

Comment hidden because of low score. Click to expand.
0

Erasmus is right.
For n=3, following above 'correct' formula - f(n)=2*f(n-1)+f(n-2), f(1)=3, f(2)=9
f(3) = 2 * 9 + 3
f(3) = 21

According to permutation logic-
1 2 3 - 3 places, 3 characters - total 3^3 = 27 permutations.
unwanted permutations - 1 2 3 having a b c -> 1 location possible. a b c can be permuted amongst each other at positions [1 2 3] in (nPr ways) - 3P3 ways = 3!

final ans = Total permutations - unwanted permutations
final ans = 27 - 6
final ans = 21

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)) {
} else {
}

for (Character c : chars) {
print(n, s + c);
}
}``````

Comment hidden because of low score. Click to expand.
0

System.out.println(s);

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}
}
}

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])));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}``````

Comment hidden because of low score. Click to expand.
0

Bonus points for reading the question.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Sorry for the lack of formatting in the code.

Also, there should not be any separators in the depth n=2 nodes in the example of the tree.

Comment hidden because of low score. Click to expand.
0

Actually, the formula is incorrect...it should actually be

``S(N)=2*(# nodes at height N-1 whose value does not equal their parent's) + 3*(# nodes at height N-1 whose value equals their parents)``

Comment hidden because of low score. Click to expand.
0

I think S(4) is 17:
aaaa
aaab
aaac
aaba
aabb
aaca
aacc
abaa
abab
abba
abbb
abbc
acaa
acac
acca
accb
accc

By now I have seen at least 4 ppl suggest this same formula. For n=4, this formula would return 3^4 - 6*2 = 69. That means there should be 23 strings as opposed to the 17 strings that I counted. Can someone confirm what's the answer for n=4?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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!

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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);
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

Consider string prefix "abb". You can append all 3 characters to it, so you have 3 options in this case.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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();
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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 );``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}
}

Comment hidden because of low score. Click to expand.
0

call: FindStrings("", "abc", 4);
results:
aaaa
aaab
aaac
aaba
aabb
aaca
aacc
abaa
abab
abba
abbb
abbc
acaa
acac
acca
accb
accc
baaa
baab
baac
baba
babb
bbaa
bbab
bbba
bbbb
bbbc
bbcb
bbcc
bcbb
bcbc
bcca
bccb
bccc
caaa
caab
caac
caca
cacc
cbba
cbbb
cbbc
cbcb
cbcc
ccaa
ccac
ccbb
ccbc
ccca
cccb
cccc

Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
} else if( !past.contains( c ) ){
if( past.size() == 3 ) {
past.clear();
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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.