Interview Question
Country: United States
function goodStrNo($str, $a, $b, $c) {
$goodStringCount = 0;
$totalC = [];
$initialA = "";
$totalconsecutiveA = 0;
$increment = true;
$initialB = "";
$incrementForB = true;
for ($i = 0; $i < strlen($str); $i++) {
if ($str[$i] === $b) {
if ($str[$i+1] === $b || $str[$i+2] === $b) {
$incrementForB = false;
}
}
$initialA = $str[$i];
if ($initialA === $a) {
$totalconsecutiveA++;
} else {
$totalconsecutiveA = 0;
}
if ($totalconsecutiveA > 2) {
$increment = false;
}
if ($str[$i] === $c) {
array_push($totalC, $str[$i]);
}
}
if (count($totalC) < 4) {
$goodStringCount++;
}
if ($increment) {
$goodStringCount++;
}
if ($incrementForB) {
$goodStringCount++;
}
return $goodStringCount;
}
int getNumberOfGoodStrings(int N){
char [] charArray = new char [N];
return getNumberOfGoodStrings(N,0,0,charArray);
}
private int getNumberOfGoodStrings(int N, int index, int Ccount, char [] charArray){
if(index == N)return 1;
int count = 0;
if(index - 2 < 0 || charArray[index - 2] != 'A'){
charArray[index] = 'A';
count += getNumberOfGoodStrings(N,index + 1, Ccount, charArray);
}
if((index - 2 >= 0 && charArray[index - 2] != 'B' && harArray[index - 1] != 'B') ||
(index == 1 && charArray[0] != 'B') ||
index == 0){
charArray[index] = 'B';
count += getNumberOfGoodStrings(N,index + 1, Ccount, charArray);
}
if(Ccount < 4){
charArray[index] = 'C';
count += getNumberOfGoodStrings(N,index + 1, Ccount + 1, charArray);
}
return count;
}
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class PrettyString
{
public static void Main(String[] args)
{
InitVar();
int N = 100;
var res = countStr(N);
Console.WriteLine(res);
Console.ReadLine();
}
private static void InitVar()
{
m1 = new long[8, 4] { { 1, 0, 0, 0 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 }, { 0, 1, 0, 0 }, { 0, 1, 0, 0 }, { 0, 0, 1, 0 } };
m2 = new long[8, 4];
getstr = new Dictionary<int, String>();
getrow = new Dictionary<String, int>();
}
static long[,] m1;// = new long[8,4]{ { 1, 0, 0, 0 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 }, { 0, 1, 0, 0 }, { 0, 1, 0, 0 }, { 0, 0, 1, 0 } };
static long[,] m2;// = new long[8,4];
static Dictionary<int, String> getstr;// = new Dictionary<int, String>();
static Dictionary<String, int> getrow;// = new Dictionary<String, int>();
public static long countStr(int N)
{
if (N == 1) return 3;
fillHm();
for (int k = 0; k < N - 2; k++)
{
// adding A
for (int i = 0; i < 8; i++)
{
if (can_Add(getstr[i], 'A'))
{
String temp = getstr[i];
temp = temp + "A";
int row = getrow[temp.Substring(1)];
for (int j = 0; j < 4; j++)
m2[row,j] += m1[i,j];
}
}
//adding B
for (int i = 0; i < 8; i++)
{
if (can_Add(getstr[i], 'B'))
{
String temp = getstr[i];
temp = temp + "B";
int row = getrow[temp.Substring(1)];
for (int j = 0; j < 4; j++)
m2[row,j] += m1[i,j];
}
}
//adding C
for (int i = 0; i < 8; i++)
{
String temp = getstr[i];
temp = temp + "C";
int row = getrow[temp.Substring(1)];
for (int j = 0; j < 3; j++)
m2[row,j + 1] += m1[i,j];
}
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 4; j++)
{
m1[i,j] = m2[i,j];
m2[i,j] = 0;
}
}
}
return sum(m1);
}
public static bool can_Add(String s, char a)
{
if (a == 'A')
{
if (s.Equals("AA"))
return false;
else
return true;
}
else
{
if (s[0] == 'B' || s[1] == 'B')
return false;
else
return true;
}
}
public static void fillHm()
{
getstr.Add(0, "AA");
getstr.Add(1, "AB");
getstr.Add(2, "AC");
getstr.Add(3, "BA");
getstr.Add(4, "BC");
getstr.Add(5, "CA");
getstr.Add(6, "CB");
getstr.Add(7, "CC");
getrow.Add("AA", 0);
getrow.Add("AB", 1);
getrow.Add("AC", 2);
getrow.Add("BA", 3);
getrow.Add("BC", 4);
getrow.Add("CA", 5);
getrow.Add("CB", 6);
getrow.Add("CC", 7);
}
public static long sum(long[,] m)
{
long s = 0;
//for (long[] a:m)
// for (long aa:a)
// s += aa;
for (long outer = 0; outer < m.GetLongLength(0); outer++)
for (long inner = 0; inner < m.GetLongLength(1); inner++)
s += m[outer,inner];
return s;
}
}
function maxNumGoodStrings(N) {
let memo = {};
function add( str, c_s ) {
if (str.length === N) {
return 1;
}
let key = str.length +
":" + c_s +
":" + (str[str.length - 1] === "A") +
":" + (str[str.length - 1] === "B") +
":" + (str[str.length - 2] === "B");
if (!memo[key]) {
count = 0;
if (c_s < 4) {
str.push("C");
count += add(str, c_s + 1);
str.pop("C");
}
if (str[str.length - 1] !== "A") {
str.push("A");
count += add(str, c_s);
str.pop("A");
}
if (str[str.length - 1] !== "B" && str[str.length - 2] !== "B") {
str.push("B");
count += add(str, c_s);
str.pop("B");
}
memo[key] = count;
}
return memo[key];
}
return add([], 0);
}
I am not sure of the 1sec time constraint for large N. The big o notation is probably o(n).
- demo April 19, 2020