Google Interview Question
Software Engineer / DevelopersTeam: None
Country: United States
Interview Type: Phone Interview
O(n) solution is provided.
We can divide strings in two types;
A type which does not contain ‘b’
and B type which contain ‘b’.
We can define matrix A and B as follows.
A[i]: the number of strings of length i in A type.
B[i]: the number of strings of length i in B type.
And the answer is A[n] + B[n]
Because B type strings with lengh i can be generated
by picking any sting in A type strings with length i-1,
and put ‘b’ in any position in the string.
There are total i positions to insert ‘b’,
thus, following equation holds between A[i] and B[i].
B[i] = i * A[i-1]
So, it is enough to compute A[i].
For considering strings in A, there are three possible
prefixes which end with ‘a’.
(because there is no constraint in the substring after ‘a’)
1. ‘a’ + A type strings with length i - 1
2. ‘ca’ + A type strings with length i - 2
3. ‘cca’ + A type strings with length i - 3
i.e., A[i] = A[i-1] + A[i-2] + A[i-3]
where A[1] = 2, A[2] = 4, A[3] = 7
We can compute matrix A iteratively.
As an example, the number of strings of length 3 is
A[3] + B[3] = A[3] + 3 * A[2] = 7 + 3*4 = 19.
int countStr(int n)
{
vector<int> A;
A.reserve(n + 1);
A[0] = 1, A[1] = 2, A[2] = 4, A[3] = 7;
for(int i = 4; i <= n; i++){
A[i] = A[i-1] + A[i-2] + A[i-3];
}
return A[n] + n*A[n-1];
}
A DP solution with inputs as the number of characters left, whether b has already been used in the built prefix and trailing number of c in the built prefix:
val memo = mutable.HashMap[(Int, Boolean, Byte), Long]()
memo.put((1, true, 0), 2l)
memo.put((1, true, 1), 2l)
memo.put((1, true, 2), 1l)
memo.put((1, false, 0), 3l)
memo.put((1, false, 1), 3l)
memo.put((1, false, 2), 2l)
def getCount(n: Int, containsB: Boolean, endC: Byte): Long = {
memo.get((n, containsB, endC)) match {
case Some(x) => return x
case None => {
var ans = 0l
if (!containsB)
ans += getCount(n - 1, true, 0)
if (endC < 2)
ans += getCount(n - 1, containsB, (endC + 1).toByte)
ans += getCount(n - 1, containsB, 0)
ans
}
}
}
println(getCount(3, false, 0))
public static void main(String arr[])
{
System.out.println(count(new String(), 3));
}
public static int count(String str, int count)
{
int sum = 0;
if (count <= 0)
{
System.out.println(str);
return 1;
}
if (str.indexOf('b') == -1)
{
sum = sum + count(str + "a", count - 1);
sum = sum + count(str + "b", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
} else
{
sum = sum + count(str + "a", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
}
return sum;
}
public static void main(String arr[])
{
System.out.println(count(new String(), 3));
}
public static int count(String str, int count)
{
int sum = 0;
if (count <= 0)
{
System.out.println(str);
return 1;
}
if (str.indexOf('b') == -1)
{
sum = sum + count(str + "a", count - 1);
sum = sum + count(str + "b", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
} else
{
sum = sum + count(str + "a", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
}
return sum;
}
public static void main(String arr[])
{
System.out.println(count(new String(), 3));
}
public static int count(String str, int count)
{
int sum = 0;
if (count <= 0)
{
System.out.println(str);
return 1;
}
if (str.indexOf('b') == -1)
{
sum = sum + count(str + "a", count - 1);
sum = sum + count(str + "b", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
} else
{
sum = sum + count(str + "a", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
}
return sum;
}
package main
import (
"fmt"
"strings"
)
func main() {
fmt.Println(count(3))
}
func count(chars_length int, args...string) int {
prefix := ""
if len(args) == 1 {
prefix = args[0]
}
if chars_length == 0 {
return 1
}
sum := 0
if !strings.Contains(prefix, "b") {
sum += count(chars_length-1, prefix+"b")
}
sum += count(chars_length-1, prefix+"a")
c_count := 0
for _, r := range prefix {
if r == 'c' {
c_count += 1
}
}
if (c_count < 2) {
sum += count(chars_length-1, prefix+"c")
}
return sum
}
package main
import (
"fmt"
"strings"
)
func main() {
fmt.Println(count(3))
}
func count(chars_length int, args...string) int {
prefix := ""
if len(args) == 1 {
prefix = args[0]
}
if chars_length == 0 {
return 1
}
sum := 0
if !strings.Contains(prefix, "b") {
sum += count(chars_length-1, prefix+"b")
}
sum += count(chars_length-1, prefix+"a")
c_count := 0
for _, r := range prefix {
if r == 'c' {
c_count += 1
}
}
if (c_count < 2) {
sum += count(chars_length-1, prefix+"c")
}
return sum
}
@interface StringCounter: NSObject
+(NSInteger)countStrings:(NSInteger) n;
@end
@implementation StringCounter
+(NSInteger)countStrings:(NSInteger) n {
if (n==1) {
return 3;
}
if (n==2) {
return 4;
}
if (n==3) {
return 19;
}
// Use N=3 case to build upon.
// Strings ending in A, not containing B: "AAA", "ACA", "CAA", "CCA"
NSInteger ANotContainB = 4;
// Strings ending in A, containing B: "ABA", "BAA", "BCA", "CBA"
NSInteger AContainB = 4;
// Strings ending in Ac, containing B: "BAC"
NSInteger AcContainB = 1;
// Strings ending in Ac, not containing B:"AAC", "CAC"
NSInteger AcNotContainB = 2;
// Strings ending in Cc, containing B:"BCC"
NSInteger CcContainB = 1;
// Strings ending in Cc, not containing B:"ACC"
NSInteger CcNotContainB = 1;
// Strings ending in Bc: "ABC", "CBC"
NSInteger Bc = 2;
// Strings ending in B: "AAB", "ACB", "CAB", "CCB"
NSInteger B = 4;
// Use calculations of prev counts for current counts, n - 3 times.
for (NSInteger i = 4; i <= n; i++) {
// Make temporary copies.
NSInteger prevANotContainB = ANotContainB;
NSInteger prevAContainB = AContainB;
NSInteger prevAcContainB = AcContainB;
NSInteger prevAcNotContainB = AcNotContainB;
NSInteger prevCcContainB = CcContainB;
NSInteger prevCcNotContainB = CcNotContainB;
NSInteger prevBc = Bc;
NSInteger prevB = B;
ANotContainB = prevAcNotContainB + prevCcNotContainB + prevANotContainB;
AContainB = prevAcContainB + prevCcContainB + prevBc + prevAContainB + prevB;
AcContainB = prevAContainB;
AcNotContainB = prevANotContainB;
CcContainB = prevAcContainB + prevBc;
CcNotContainB = prevAcNotContainB;
Bc = prevB;
B = prevAcNotContainB + prevCcNotContainB + prevANotContainB;
}
return ANotContainB + AContainB + AcContainB + AcNotContainB + CcContainB + CcNotContainB + Bc + B;
}
@end
Iterative DP solution in Python:
def count(l):
D = [[[None]*3 for i in xrange(2)] for j in xrange(l)]
D[0][0][0] = 1
D[0][0][1] = 1
D[0][0][2] = 0
D[0][1][0] = 1
D[0][1][1] = 0
D[0][1][2] = 0
for i in xrange(1, l):
for char in ["a", "b", "c"]:
if char == "a":
D[i][0][0] = D[i-1][0][0]
D[i][0][1] = D[i-1][0][1]
D[i][0][2] = D[i-1][0][2]
D[i][1][0] = D[i-1][1][0]
D[i][1][1] = D[i-1][1][1]
D[i][1][2] = D[i-1][1][2]
elif char == "b":
D[i][1][0] += D[i-1][0][0]
D[i][1][1] += D[i-1][0][1]
D[i][1][2] += D[i-1][0][2]
elif char == "c":
D[i][0][1] += D[i-1][0][0]
D[i][1][1] += D[i-1][1][0]
D[i][0][2] += D[i-1][0][1]
D[i][1][2] += D[i-1][1][1]
print D
return sum(D[l-1][0])+sum(D[l-1][1])
Iterative DP-solution in Python:
def count(l):
D = [[[None]*3 for i in xrange(2)] for j in xrange(l)]
D[0][0][0] = 1
D[0][0][1] = 1
D[0][0][2] = 0
D[0][1][0] = 1
D[0][1][1] = 0
D[0][1][2] = 0
for i in xrange(1, l):
for char in ["a", "b", "c"]:
if char == "a":
D[i][0][0] = D[i-1][0][0]
D[i][0][1] = D[i-1][0][1]
D[i][0][2] = D[i-1][0][2]
D[i][1][0] = D[i-1][1][0]
D[i][1][1] = D[i-1][1][1]
D[i][1][2] = D[i-1][1][2]
elif char == "b":
D[i][1][0] += D[i-1][0][0]
D[i][1][1] += D[i-1][0][1]
D[i][1][2] += D[i-1][0][2]
elif char == "c":
D[i][0][1] += D[i-1][0][0]
D[i][1][1] += D[i-1][1][0]
D[i][0][2] += D[i-1][0][1]
D[i][1][2] += D[i-1][1][1]
print D
return sum(D[l-1][0])+sum(D[l-1][1])
Iterative Python solution:
def is_c_usable(string):
if len(string)<2:
return True
return string[-2:]!="cc"
def valid_strings_iterative(n):
# O(2^n)
# Format of tuple is (string, isBAvailable)
strings = [("a", True), ("b", False), ("c", True)]
for i in xrange(1, n):
new_strings = []
for string, b_available in strings:
new_strings.append((string+"a", b_available))
if b_available==True:
new_strings.append((string+"b", False))
if is_c_usable(string)==True:
new_strings.append((string+"c", b_available))
strings = new_strings
return [s[0] for s in strings]
I'm pretty sure this one can be O(lg N) and O(1) via divide and conquer and dynamic programming, but the code seems like it would be very complicated.
(Basically, try all possible middle 2 or 3 characters so sides are each exactly floor((N-2)/2) long; this makes all recursive calls go to the same value of N so call tree is lg N height; only # of 3's on right * # of 3's on left * b allowed = 3*3*2 = 18 calls need to be memo-ized for each used value of N.)
private static final String[] availableChars = {"A", "B", "C"};
public static void main(String[] args){
TreeSet<String> combinations = getCombinations(5);
TreeSet<String> filteredCombinations = filter(combinations);
System.out.println(filteredCombinations);
}
private static TreeSet<String> filter(TreeSet<String> input){
TreeSet<String> output = new TreeSet<>();
for (String s : input){
if (!s.contains("CCC")){
if (s.indexOf('B') == s.lastIndexOf('B')) {
output.add(s);
}
}
}
return output;
}
private static TreeSet<String> getCombinations(int length){
TreeSet<String> output = new TreeSet<>();
if (length <= 1){
for (String character : availableChars) {
output.add(character);
}
}else {
TreeSet<String> set = getCombinations(length - 1);
for (String s : set) {
for (String character : availableChars) {
output.add(character + s);
}
}
}
return output;
}
Let's say F(N) is the number of such words with length N and G(N) is the number of words not containing any 'b'.
F(0) = 1
F(1) = 3 // 'a' 'b' 'c'
F(2) = 8 // 'aa' 'ab' 'ac' 'cc' 'ca' 'cb' 'ba' 'bc'
G(0) = 1
G(1) = 2 // 'a' 'b'
G(2) = 4 // 'aa' 'ac' 'cc' 'ca'
Now let's see how our words from the problem can begin:
1. a... F(N-1) such words
2. cca... F(N-3) such words
3. ca... F(N-2) such words
4. b... G(N-1) such words
5. cb... G(N-2) such words
6. ccb... G(N-3) such words
Taking similar path with G words, we can see that G(N) = G(N-1) + G(N-2) + G(N-3)
So, finally
F(N) = F(N-1) + F(N-2) + F(N-3) + G(N-1) + G(N-2) + G(N-3)
Proof by example (not really a proof):
F(3) = 8 + 3 + 1 + 4 + 2 + 1 = 19
import java.util.HashMap;
public class ABCs {
HashMap <String, Integer> h = new HashMap <String, Integer> ();
int howManyStrings (int n ){
int total = howManyStrings (n,false,0);
return total;
}
int howManyStrings (int n, Boolean hasBbeenUsed, int trailingCs){
if ( n == 0) return 0;
int total=0;
if (n == 1){
total = 1; //a
if (!hasBbeenUsed) total++; // b
if ( trailingCs < 2 ) total++; // c
return total;
}
else{
//Check if we considered this case already.
String s = n + hasBbeenUsed.toString() + trailingCs;
if ( h.containsKey(s) ) return h.get(s);
total=
howManyStrings (n-1, hasBbeenUsed, 0); //a.
if (!hasBbeenUsed) total+= howManyStrings (n-1, true, 0); //b
if ( trailingCs < 2) total+= howManyStrings (n-1, hasBbeenUsed, trailingCs++); //Final c.
h.put (s, total);
return total;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a = new ABCs().howManyStrings (20);
System.out.println(a);
}
}
This can be done in O(n) time using DP... we just need to keep track of 4 variables and update them in each iteration.
totalPrev= total result previous value of n
total1cs=total numbers with 1 c in the last two positions
total2cs=total numbers with 2 c in the last two positions
totalBPrev=total numbers which already have b in them..
here is the code which included logic for updates (quite self explanatory so I am not writing it down) ...
public static int findStrings(int n){
if(n==0)
return 0;
if(n==1)
return 3;
if(n==2)
return 8;
int k=2;
int totalPrev=8;
int total1cs=2;
int total2cs=1;
int totalBPrev=4;
while(k<n){
k++;
int newTotal=3*totalPrev-totalBPrev-total2cs;
int t2csnew=total1cs;
total1cs=totalPrev-total1cs-total2cs;
total2cs=t2csnew;
totalBPrev=totalPrev;
totalPrev=newTotal;
}
return totalPrev;
}
public class Solution
{
public static void main(String[] args)
{
Solution s = new Solution();
System.out.println(s.numberOfStr(9));
}
public int numberOfStr(int n) {
return dfs('a', false, 0, n, 0);
}
private int dfs(char current, boolean hasB, int level, int n, int continueC) {
if (level == n) return 1;
int sum = 0;
sum += dfs('a', hasB, level+1, n, 0);
if (!hasB) sum += dfs('b', true, level+1, n, 0);
if (continueC < 2) {
if (current == 'c') sum += dfs('c', hasB, level+1, n, continueC+1);
else sum += dfs('c', hasB, level+1, n, 1);
}
return sum;
}
}
public class PrintAllPerms {
public static void main(String[] args) {
printAllStringCombinations("abc".toCharArray(), 3);
}
public static void printAllStringCombinations(char[] s, int size) {
List<String> l = getCombinations(s, size);
// filter out invalid strings
List<String> invalidList = new ArrayList<>();
for (String st : l) {
if (!isValid(st)) {
invalidList.add(st);
}
}
l.removeAll(invalidList);
for (String string : l) {
System.out.println(string );
}
}
private static boolean isValid(String st) {
char[] c = st.toCharArray();
int countBs = 0;
int countConsecutiveCs = 0;
for (int i = 0; i < c.length; i++) {
if (c[i] == 'b') {
countBs++;
} else if (c[i] == 'c' && i + 1 < c.length && c[i+1] == 'c') {
countConsecutiveCs++;
}
}
if (countBs > 1 || countConsecutiveCs > 1) {
return false;
}
return true;
}
public static List<String> getCombinations(char[] c, int size) {
List<String> r = new ArrayList<>();
generateCombinations(r, new StringBuilder(), c, size);
return r;
}
public static void generateCombinations(List<String> list, StringBuilder sb, char[] c, int size) {
if (sb.length() == size) {
list.add(sb.toString());
} else {
for (int i = 0; i < c.length; i++) {
sb.append(c[i]);
generateCombinations(list, new StringBuilder(sb.toString()), c, size);
sb.deleteCharAt(sb.length() - 1);
}
}
}
}
Using recursion:
define s(n): total number of valid cases with length n
define a(n): number of valid cases with length n starting with 'a'
define b(n): '' with 'b'
define c(n): '' with 'c'
base cases:
a(1) = 1 // "a" is the only valid string of length 1
b(1) = 1 // "b"
c(1) = 1 // "c"
s(1) = a(1) + b(1) + c(1)
s(n) = a(n) + b(n) + c(n) // the string can start with either a, b or c
a(n) = s(n-1) // "a" + any valid string of length n-1
b(n) = 1 + (n-1) + (n-2) // if "b" is the first character, the remaining string only consists of 'a' and 'c'.
// 1 is for "b" + "aaaa....a" is the only valid string with no 'c'
// (n-1) is for "b" + any valid string of length n-1 with only one 'c'
// (n-2) is for "b" + any valid string of length n-1 with only one 'cc'
c(n) = s(n-1) - 1 (if n >2)// "c" + any valid sting of length n-1 except for 'cc????'
= s(n-1) (if (n <= 2)
int a(int n) {
if (n == 1) return 1;
else return s(n-1);
}
int b(int n) {
if (n == 1) return 1;
else return 1 + (n-1) + (n-2);
}
int c(int n) {
if (n == 1) return 1;
else if (n == 2) return s(n-1);
else return s(n-1) - 1;
}
int s(int n) {
return a(n) + b(n) + c(n);
}
s(3) = a(3) + b(3) + c(3)
= s(2) + 4 + s(2) -1 = 2 * s(2) + 3
s(2) = a(2) + b(2) + c(2)
= s(1) + 2 + s(1) = 2 * s(1) + 2
s(1) = a(1) + b(1) + c(1) = 1 + 1+ 1 = 3
Therefore, s(2) = 2 * 3 + 2 =8
s(3) = 2 * 8 + 3 = 19 // correct
public class GenerateStringsOneBTwoConsecutiveC
{
public static void main(String[] args)
{
generate(new StringBuilder(""), 50, 0);
}
public static void generate(StringBuilder sb, int len, int numB)
{
if (numB >= 2)
{
return;
}
int strLen = sb.length();
if (strLen >= 3 && sb.charAt(strLen - 1) == 'c' &&
sb.charAt(strLen - 2) == 'c' && sb.charAt(strLen - 3) == 'c')
{
return;
}
if (strLen >= len)
{
System.out.println(sb);
return;
}
//A
generate(sb.append('a'), len, numB);
sb.deleteCharAt(sb.length() - 1);
//B
generate(sb.append('b'), len, numB + 1);
sb.deleteCharAt(sb.length() - 1);
//C
generate(sb.append('c'), len, numB);
sb.deleteCharAt(sb.length() - 1);
}
}
public class GenerateStringsOneBTwoConsecutiveC
{
public static void main(String[] args)
{
generate(new StringBuilder(""), 50, 0);
}
public static void generate(StringBuilder sb, int len, int numB)
{
if (numB >= 2)
{
return;
}
int strLen = sb.length();
if (strLen >= 3 && sb.charAt(strLen - 1) == 'c' &&
sb.charAt(strLen - 2) == 'c' && sb.charAt(strLen - 3) == 'c')
{
return;
}
if (strLen >= len)
{
System.out.println(sb);
return;
}
//A
generate(sb.append('a'), len, numB);
sb.deleteCharAt(sb.length() - 1);
//B
generate(sb.append('b'), len, numB + 1);
sb.deleteCharAt(sb.length() - 1);
//C
generate(sb.append('c'), len, numB);
sb.deleteCharAt(sb.length() - 1);
}
}
public class GenerateStringsOneBTwoConsecutiveC
{
public static void main(String[] args)
{
generate(new StringBuilder(""), 50, 0);
}
public static void generate(StringBuilder sb, int len, int numB)
{
if (numB >= 2)
{
return;
}
int strLen = sb.length();
if (strLen >= 3 && sb.charAt(strLen - 1) == 'c' &&
sb.charAt(strLen - 2) == 'c' && sb.charAt(strLen - 3) == 'c')
{
return;
}
if (strLen >= len)
{
System.out.println(sb);
return;
}
//A
generate(sb.append('a'), len, numB);
sb.deleteCharAt(sb.length() - 1);
//B
generate(sb.append('b'), len, numB + 1);
sb.deleteCharAt(sb.length() - 1);
//C
generate(sb.append('c'), len, numB);
sb.deleteCharAt(sb.length() - 1);
}
}
public class StringPermute {
public static void main(String... args) {
int[] result= new int[]{0};
find("",0,0,3, result);
System.out.println(result[0]);
}
static void find(String s, int countb, int countc, int n, int[] result) {
if (n == 0) {
result[0]++;
return;
}
for (char c: "abc".toCharArray()) {
int newCountb = countb;
int newCountc = countc;
if (c =='b') newCountb ++;
if (c == 'c') newCountc++;
else newCountc = 0;
if (newCountb > 1) continue;
if (newCountc == 3) continue;
find(s + c, newCountb, newCountc, n-1, result);
}
}
}
public class StringPermute {
public static void main(String... args) {
int[] result= new int[]{0};
find("",0,0,3, result);
System.out.println(result[0]);
}
static void find(String s, int countb, int countc, int n, int[] result) {
if (n == 0) {
result[0]++;
return;
}
for (char c: "abc".toCharArray()) {
int newCountb = countb;
int newCountc = countc;
if (c =='b') newCountb ++;
if (c == 'c') newCountc++;
else newCountc = 0;
if (newCountb > 1) continue;
if (newCountc == 3) continue;
find(s + c, newCountb, newCountc, n-1, result);
}
}
}
It is permutation problem with conditions.
The number of permutations which contain 2 c's is n*(n-1).
The number of permutations which contain 1 b's and 1 c's is n*(n-1) + n
The number of permutations which does not contain c is n-1
The number of permutations which does not contain b is n-1
Adding all these we get the formula 2(n^2) + n - 2.
This is a permutation problem with conditions.
The number of permutations with 2 c's is n*(n-1)
The number of permutations with 1 b and 1 c is n*(n-1) + n
The number of permutations with 1 c is n
The number of permutations with no b and no c is 1.
Adding all these we get the formual 2(n^2) + 1
- Basic logic is to create permutation set but just add the additional condition given to avoid those possibilities of consecutive more than 2 'c' and allow only one instance of 'b'.
public class PermutationSpecial {
public int count = 0;
void permutationSet(StringBuilder strBuilder, String str, int index, HashMap<Character, Integer> soFarMap) {
if (index == strBuilder.length()) {
System.out.println(strBuilder.toString());
count++;
return;
}
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'b' && soFarMap.containsKey('b')) {
continue;
}
if (str.charAt(i) == 'c' && (index > 1 && strBuilder.charAt(index - 1) == 'c'
&& strBuilder.charAt(index - 2) == 'c')) {
continue;
}
strBuilder.setCharAt(index, str.charAt(i));
// add the hashset to allow to look back.
if (soFarMap.containsKey(str.charAt(i)) != true) {
soFarMap.put(str.charAt(i), 1);
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) + 1);
}
permutationSet(strBuilder, str, index + 1, soFarMap);
if (soFarMap.get(str.charAt(i)) == 1) {
soFarMap.remove(str.charAt(i));
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) - 1);
}
}
}
public static void main(String [] args) {
PermutationSpecial permutationSpecial = new PermutationSpecial();
String str = new String("abc");
StringBuilder strBuilder = new StringBuilder(3);
strBuilder.append('a');
strBuilder.append('b');
strBuilder.append('c');
HashMap<Character, Integer> soFarMap = new HashMap<>();
permutationSpecial.permutationSet(strBuilder, str, 0, soFarMap);
System.out.println(permutationSpecial.count);
}
}
Resubmitting with code brackets.
/**
* Created by dhavalp on 9/1/16.
*/
public class PermutationSpecial {
public int count = 0;
void permutationSet(StringBuilder strBuilder, String str, int index, HashMap<Character, Integer> soFarMap) {
if (index == strBuilder.length()) {
System.out.println(strBuilder.toString());
count++;
return;
}
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'b' && soFarMap.containsKey('b')) {
continue;
}
if (str.charAt(i) == 'c' && (index > 1 && strBuilder.charAt(index - 1) == 'c'
&& strBuilder.charAt(index - 2) == 'c')) {
continue;
}
strBuilder.setCharAt(index, str.charAt(i));
// add the hashset to allow to look back.
if (soFarMap.containsKey(str.charAt(i)) != true) {
soFarMap.put(str.charAt(i), 1);
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) + 1);
}
permutationSet(strBuilder, str, index + 1, soFarMap);
if (soFarMap.get(str.charAt(i)) == 1) {
soFarMap.remove(str.charAt(i));
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) - 1);
}
}
}
public static void main(String [] args) {
PermutationSpecial permutationSpecial = new PermutationSpecial();
String str = new String("abc");
StringBuilder strBuilder = new StringBuilder(3);
strBuilder.append('a');
strBuilder.append('b');
strBuilder.append('c');
HashMap<Character, Integer> soFarMap = new HashMap<>();
permutationSpecial.permutationSet(strBuilder, str, 0, soFarMap);
System.out.println(permutationSpecial.count);
}
}
It can be solved by 2 process.
1) split to 2 strings by possible position of 'b'
2) strings with 'a' and 'c' with no more than 2 consecutive 'c's
1)
When length = 3
Possible b positions are
1. no b ___
2. b at 0 b__
3. b at 1 _b_
4. b at 2 __b
So the answer is 1 + 2 + 3 + 4 where __ is a string consist by 'a' and 'c' with no more than 2 consecutive 'c's.
2) For given string s
let x = # of permutations
let y = # of permutations ended with 'ac' (or 'c')
let z = # of permutations ended with 'cc'
and let
x0 = 0
y0 = 0
z0 = 0
and
x1 = 2 ("a", "c")
y1 = 1 ("c")
z1 = 0
Then
xn+1, yn+1, zn+1 can be defined as
xn+1 = (xn * 2) - zn
yn+1 = xn - zn
zn+1 = yn - zn
So the final answer is when length is 3
x3 + (x0 + x2) + (x1 + x1) + (x2 + x0)
7 + 4 + 4 + 4 = 19.
Complexity is O(n).
int count (String s, int l, int consecutiveC, boolean bUsed, int n) {
if(l == n ) {
System.out.println(s);
return 1;
}
int c1 =0;
int c2 = 0;
int c3 =0;
//use 'a'
c1 = count(s+'a', l+1, 0, bUsed, n);
if(consecutiveC < 2) {
// use 'c'
c2 = count(s+'c', l+1, consecutiveC+1, bUsed, n );
}
if(!bUsed) {
// use 'b'
c3 = count(s+'b', l+1, 0, true, n);
}
return c1+c2+c3;
}
public static int count(int n) {
// total, not excluding more than 2 consecutive c's
int t = (int)Math.pow(2, n-1) * (2 + n);
// remove all consecutive c's of count 3 or more. Each time
// there are (n-t) + 1 possibilities of t consecutive c's, and
// in the rest of the positions, there can be at most 0 or 1 b (rest are a's)
// so its (n-t+1) options again, so multiply.
for(int i = n-2; i >= 1; i--) {
t -= (i * i);
}
return t;
}
public static int count(int n) {
// total, not excluding more than 2 consecutive c's
int t = (int)Math.pow(2, n-1) * (2 + n);
// remove all consecutive c's of count 3 or more. Each time
// there are (n-t) + 1 possibilities of t consecutive c's, and
// in the rest of the positions, there can be at most 0 or 1 b (rest are a's)
// so its (n-t+1) options again, so multiply.
for(int i = n-2; i >= 1; i--) {
t -= (i * i);
}
return t;
}
public static void Permutations(string prefix, int n, bool bUsedEarlier, bool cExhaustedEarlier, ref int count)
{
char[] chars = { 'a', 'b', 'c' };
if (n == 0)
{
Console.WriteLine(prefix);
count++;
return;
}
foreach (var @char in chars)
{
if (@char == 'b' && bUsedEarlier)
continue;
if (@char == 'c' && cExhaustedEarlier)
continue;
var bUsed = bUsedEarlier || @char == 'b';
var cExhausted = cExhaustedEarlier || prefix.Length > 0 && prefix[prefix.Length - 1] == 'c' && @char == 'c';
Permutations(prefix + @char, n - 1, bUsed, cExhausted, ref count);
}
}
public static void StringTest()
{
int count = 0;
Permutations("", 4, false, false, ref count);
Console.WriteLine("Count of Permutations: " + count);
}
Simple/Naive C recursive code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void code(char* arr, char* st, char* ret, int b, int c){
static int cnt = 0;
int len = strlen(ret);
if(!(*ret)){
cnt++;
printf("%d: %s \n", cnt, st);
return;
}
for(int i=0; i<sizeof(arr); i++){
if(i == 0){
ret[0] = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, b, x);
}
if(i == 1 && b != 0){
ret[0] = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, 0, x);
}
if(i == 2 && c != 0){
ret[0] = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, b, c-1);
}
}
}
int main()
{
char arr[] = {'a', 'b', 'c'};
int size = 3;
char* ret = malloc(sizeof(char)*size+1);
*(ret+sizeof(char)*size+1) = '\n';
char* st = ret;
memset(st, 'x', size);
code(arr, st, ret, 1, 2);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void code(char* arr, char* st, char* ret, int b, int c){
static int cnt = 0;
int len = strlen(ret);
if(!(*ret)){
cnt++;
printf("%d: %s \n", cnt, st);
return;
}
for(int i=0; i<sizeof(arr); i++){
if(i == 0){
ret[0] = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, b, x);
}
if(i == 1 && b != 0){
ret[0] = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, 0, x);
}
if(i == 2 && c != 0){
ret[0] = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, b, c-1);
}
}
}
int main()
{
char arr[] = {'a', 'b', 'c'};
int size = 3;
char* ret = malloc(sizeof(char)*size+1);
*(ret+sizeof(char)*size+1) = '\n';
char* st = ret;
memset(st, 'x', size);
code(arr, st, ret, 1, 2);
return 0;
}
Using dynamic programming and writing the sequence taking one type of word at a time and adding other starting from a and following row sequence: a,c,b I found the pattern:
0 1 2 3 4 5 6
a 1 1 1 1 1 1 1
c 1 2 4 7 13 24 44
b 1 3 8 19 43 94 200
def numberofPermutations(n):
n=n+1
arr1=[0]*n
arr2=[0]*n
arr1[0]=1
arr1[1]=2
arr1[2]=4
arr2[0]=1
if n>2:
for i in xrange(3,n):
# The second column specifying a bag of a and c, follows tribonacci sequence so if only a and c: the number can be given by the second row
arr1[i]=arr1[i-1]+arr1[i-2]+arr1[i-3]
for j in xrange(1,4):
# The third column specifying a bag of a,c and b follows this sequence given below till a range upto n=3
arr2[j]=arr1[j]+j*arr1[j-1]
for j in xrange(4,n):
# The third column specifying a bag of a,c and b follows this sequence given below till for n>3
arr2[j]=arr1[j-1]+arr1[j-2]+arr1[j-3]+arr2[j-1]+arr2[j-2]+arr2[j-3]
return arr2[-1] #return last element of array
def make(n, curstr, bb, cc, result):
if len(curstr) == n:
result.append(curstr)
return
for c in "abc":
if bb and c == "b": continue
if cc and c == 'c': continue
make(n, curstr+c, 1 if c == 'b' else bb, (curstr and curstr[-1] == 'c' and c == 'c'), result)
def make_comb(n):
if not n: return
result = []
make(n, "", 0, 0, result)
return result
def make(n, curstr, bb, cc, result):
if len(curstr) == n:
result.append(curstr)
return
for c in "abc":
if bb and c == "b": continue
if cc and c == 'c': continue
make(n, curstr+c, 1 if c == 'b' else bb, (curstr and curstr[-1] == 'c' and c == 'c'), result)
def make_comb(n):
if not n: return
result = []
make(n, "", 0, 0, result)
return result
def make(n, curstr, bb, cc, result):
if len(curstr) == n:
result.append(curstr)
return
for c in "abc":
if bb and c == "b": continue
if cc and c == 'c': continue
make(n, curstr+c, 1 if c == 'b' else bb, (curstr and curstr[-1] == 'c' and c == 'c'), result)
def make_comb(n):
if not n: return
result = []
make(n, "", 0, 0, result)
return result
findstring(n) = findstring_ac(n) + n * findstring_ac(n-1)
where findstring_ac(n) is number of strings consists only of a and c, not b
And
findstring_ac(n) = fa(n) + fc(n) + fcc(n)
where
fa(n) is number of strings consists of a, c and ends with a
fc(n) is number of strings consists of a, c and ends with only one c
fcc(n) is number of strings consists of a, c and ends with double c
and
fa(1) = fc(1) = 1
fcc(1) = 0
fa(n) = fa(n-1) + fc(n-1) + fcc(n-1)
fc(n) = fa(n-1)
fcc(n) = fc(n-1)
static int count(int n) {
if (n <= 0)
return 0;
int aNoB = 1;
int cNoB = 1;
int ccNoB = 0;
int aHasB = 0;
int cHasB = 0;
int ccHasB = 0;
int endWithB = 1;
for (int i = 2; i <= n; i++) {
int new_aNoB = aNoB + cNoB + ccNoB;
int new_cNoB = aNoB;
int new_ccNoB = cNoB;
int new_aHasB = aHasB + cHasB + ccHasB + endWithB;
int new_cHasB = aHasB + endWithB;
int new_ccHasB = cHasB;
int new_endWithB = aNoB + cNoB + ccNoB;
aNoB = new_aNoB;
cNoB = new_cNoB;
ccNoB = new_ccNoB;
aHasB = new_aHasB;
cHasB = new_cHasB;
ccHasB = new_ccHasB;
endWithB = new_endWithB;
}
return aNoB + cNoB + ccNoB + aHasB + cHasB + ccHasB + endWithB;
}
Sorry about late response,
Assume n >= 4
Let R(n) = # of allowed strings of length n
T(n) = # of allowed strings of length n with no 'b's
T(n, aa) = # of allowed strings of length n with no 'b's which end in 'aa.'
Similarly define T(n, ac), T(n, ca), and T(n, cc).
Firstly, note T(n) = T(n, aa) + T(n, ac) + T(n, ca) + T(n, cc).
Secondly, looking at prefixes, we notice a recursion
T(n, cc) = T(n-2, aa) + T(n-2, ca)
T(n, ca) = T(n-2, aa) + T(n-2, ac) + T(n-2, ca)
T(n, ac) = T(n-2, aa) + T(n-2, ac) + T(n-2, ca) + T(n-2, cc)
T(n, aa) = T(n-2, aa) + T(n-2, ac) + T(n-2, ca) + T(n-2, cc)
Using dynamic programming, we can do this from bottom up. We already know T(2, aa), T(2, ac), T(2, ca), T(2, cc), T(3, aa), T(3, ac), T(3, ca), T(3, cc), so we can get T(n, aa), T(n, ac), T(n, ca), T(n, cc) for all n >= 4. Then we sum up those 4 values to get T(n).
Now, let's worry about the 'b's. Notice that a 'b' would cleave a string, one of them length k and the other one length n-1-k for some 0 =< k =< n-1. So there are T(k)*T(n-1-k) allowed strings of length n with 'b' in position k (beginning at 0). Thus we get
R(n) = T(n) + Sum(T(k)*T(n-1-k), k = 0 to n-1)
A working Python solution.
def longest_palindrome(string):
# count how many times each char shows up
count = {}
for char in string:
if char in count:
count[char] += 1
else:
count[char] = 1
# if there are multiple odds, leave only one odd
odd_appeared = False
odd_char = ""
for key in count:
if count[key] % 2 == 1:
if odd_appeared:
count[key] -= 1
else:
odd_appeared = True
odd_char = key
# go through the dictionary and reconstruct the palindrome string
palindrome = ""
for key in count:
chars = count[key]/2 * key
palindrome = palindrome + chars
palindrome = chars + palindrome
if odd_appeared:
n = len(palindrome)
palindrome = palindrome[:n/2] + odd_char + palindrome[n/2:]
return palindrome
print longest_palindrome('ttaatta')
print longest_palindrome('abc')
print longest_palindrome('aha')
print longest_palindrome('a')
print longest_palindrome('')
Sorry the last post was for a different problem. Here's the working solution in Python.
result = []
def findStrings(n):
if n == 0:
return
if n == 1:
result = ['a','b','c']
# initalize result list and two counts
current_string = ""
count_b = 0
count_c_seq = 0
# throw the values into the recusion
findStringsHelper(current_string,count_b,count_c_seq,n)
return
def findStringsHelper(current_string,count_b,count_c_seq,n):
if len(current_string) >= n:
result.append(current_string)
else:
findStringsHelper(current_string+"a",count_b,0,n)
if count_b == 0:
findStringsHelper(current_string+"b",count_b+1,0,n)
if count_c_seq < 2:
findStringsHelper(current_string+"c",count_b,count_c_seq+1,n)
findStrings(2)
print result
print len(result)
"""
a c cc with b
0 -> 0 0 0 0
1 -> 1 1 0 1
2 -> 2 1 1 1(a + c + cc)*2
3 -> 4 2 1 2*(1(a + c + cc)+ 2(a + c + cc)*0(a + c + cc))
4 -> 7 4 2
5 -> 13 7 4
"""
def total_perms(n):
if n == 0:
return 0
if n == 1:
return 3
dp = [None]*(n+1)
s0 = (0, 0, 0)
s1 = (1, 1, 0)
dp[0] = (s0, 1)
dp[1] = (s1, sum(s1))
for i in xrange(2, n+1):
temp = (dp[i-1][1], dp[i-1][0][0], dp[i-1][0][1])
dp[i] = (temp, sum(temp))
perms = dp[-1][1]
for i in xrange(n):
perms += dp[i][1]*dp[n-1-i][1]
return perms
print total_perms(4)
I'm pretty sure this one can be O(lg N) and O(1) via divide and conquer and dynamic programming, but the code seems like it would be very complicated.
(Basically, try all possible middle 2 or 3 characters so sides are each exactly floor((N-2)/2) long; this makes all recursive calls go to the same value of N so call tree is lg N height; only # of 3's on right * # of 3's on left * b allowed = 3*3*2 = 18 calls need to be memo-ized for each used value of N.)
I'm pretty sure this one can be O(lg N) and O(1) via divide and conquer and dynamic programming, but the code seems like it would be very complicated.
(Basically, try all possible middle 2 or 3 characters so sides are each exactly floor((N-2)/2) long; this makes all recursive calls go to the same value of N so call tree is lg N height; only # of 3's on right * # of 3's on left * b allowed = 3*3*2 = 18 calls need to be memo-ized for each used value of N.)
DP seems to be an overkill for this.
O(1) runtime, O(1) space
int findStrings(int n)
{
int res = 0;
// 0 'c's
res += 1; // 0 'b's
res += n; // 1 'b' in each position
// 1 'c's
res += 1 * n; // 0 'b's, 1 'c' in n pos
res += (n - 1) * n; // 1 'b' in n-1 pos, 1 'c' in n pos
// 2 'c's, (nk) pos
res += 1 * ((n - 1) * n / 2); // 0 'b's, 2 'c's in (nk) pos
res += (n - 2) * (n * (n - 1) /2); // 1 'b' in n-2 pos, 2 'c's in (nk) pos
return res;
}
- Munish September 13, 2016