# Maximum character insertion

I would like to know any suggestions about to improve my code and/or get a better approach for this problem solution and your rating of my approach to the problem.(besides removing the if statements where the amount+= 0; I'm aware that it should be there)

Description

Write a function that, given a string S consisting of N character. Returns the maximum number of letters 'a' that can be inserted into S. so that the resulting string doesn't contain three consecutive letters 'a'. If the string S contains substring 'aaa', then the function should return -1.

Examples:

1. S = "aabab" should return 3 "aabaabaa"
2. S = "dog" should return 8 "aadaaoaagaa"
3. S = "aa" should return 0
4. S = "baaaa" should return -1 S = "a" should return 1 "aa"

1. capital letters represent the original str content
2. "A" means the char the "forbidden character"
3. "B" means any other character
4. "a" means "inserted" a

The Code

        private static int  FindMaxInsert(string str)
{
int amount =0;
const char forbiddenChar = 'a';
if (str.Contains("aaa"))
{
amount = -1;
}

else
{
if (str.Length == 1)
{
if (str[0] == forbiddenChar)
amount = 1; //A - > aA || Aa
else
amount = 4; // B - > aaBaa
}
else if (str.Length == 2)
{
if ((str[0] == forbiddenChar && str[1] != forbiddenChar) || (str[0] != forbiddenChar && str[1] == forbiddenChar))
amount = 3; // A B || B A -> aABaa || aaBAa
}

else if (str.Length > 2)//prevnet  against empty string
{
if (str[0] != forbiddenChar)
amount += 2;
if (str[str.Length - 1] != forbiddenChar)
amount += 2;

for (int i = 0; i < str.Length - 2; i += 2) //search insert between
{
char first = str[i];
char middle = str[i + 1];
char last = str[i + 2];

if (first == forbiddenChar && middle == forbiddenChar && last == forbiddenChar)
amount += 0; // A A A - > cant

else if (first == forbiddenChar && middle == forbiddenChar && last != forbiddenChar)
amount += 0;  // A A B  -> cant

else if (first == forbiddenChar && middle != forbiddenChar && last == forbiddenChar)
amount += 2; // A B A  -> AaBaA

else if (first == forbiddenChar && middle != forbiddenChar && last == forbiddenChar)
amount += 0; // B A A   -> cant

else if (first == forbiddenChar && middle != forbiddenChar && last != forbiddenChar)
amount += 3; // A B B -> AaBaaB

else if (first != forbiddenChar && middle == forbiddenChar && last != forbiddenChar)
amount += 1; // B A B  - > BaAB || BAaB

else if (first != forbiddenChar && middle != forbiddenChar && last == forbiddenChar)
amount += 3;  // B B A  -> BaaBaA || BaaBAa

else if (first != forbiddenChar && middle != forbiddenChar && last != forbiddenChar)
amount += 4; // B B B -> BaaBaa
}
}
}

return amount;

}

public static void Main(string[] args)
{
Console.WriteLine("dog " + FindMaxInsert("dog"));
Console.WriteLine("aabab " + FindMaxInsert("aabab"));
Console.WriteLine("aa " + FindMaxInsert("aa"));
Console.WriteLine("a " + FindMaxInsert("a"));
Console.WriteLine("Empty " + FindMaxInsert(String.Empty));
}

• amount += 0 :o :o :o – dfhwze Jul 11 '19 at 8:11
• that's intentional, i wanted to check that I'm not missing any option – styx Jul 11 '19 at 8:18
• When you say "charterer", do you mean "character"? – Fund Monica's Lawsuit Jul 11 '19 at 22:01
• n1= number of non a characters n2= no of a,s in the string maximum no of inserion of a.'s = 2 * (n1 +1) - n2 – Rajesh Dec 9 '19 at 12:31

Your code contains a large amount of special-case handling, and as Peter Taylor already pointed out, it doesn't always produce correct results. Inputs with an even length that don't end with an a in particular, but also several odd-length inputs.

Let's take a step back and look at the problem from a different angle:

• For a string s, there are s.Length + 1 'insertion points'. Each point can hold at most two a's, so that gives you a maximum of (s.Length + 1) * 2 insertions.
• Each standalone a affects two insertion points - one to its left and one to its right. At most one a can be inserted in one of these points. Instead of 2 * 2 = 4 insertions, you now only have 1. That's a -3 reduction.
• Each aa pair affects 3 insertion points - one to their left, one to their right, and one in-between the a's. No insertions are possible in any of these points, so instead of 3 * 2 = 6, you now have 0. That's a -6 reduction, or a -3 reduction per a.
• Inputs that contain an aaa triplet are invalid.

In other words, the number of insertions can easily be calculated from the string length and the number of a's. The only special case you need to handle is the presence of an "aaa" substring.

• Your first statement is not entirely correct maximum insertion is(s.Length + 1) * 2 + 2 For example, dog 8 = 3*2 + 2(aaDaaOaaGaa), or doog = 4*2 + 2 =10(aaDaaOaaOaaGaa) – styx Jul 11 '19 at 9:58
• That's what the +1 is for. (3 + 1) * 2 == 8. – Pieter Witvoet Jul 11 '19 at 10:01
• you are right!! – styx Jul 11 '19 at 10:01
• also simply counting the 'a's it not sufficient I think, take the example "aa" which have 2 'a' but the answer is 0, or "doga" have 1 'a' but can cleary the answer is not 1 – styx Jul 11 '19 at 10:06
• I clarified my post: the answer can be calculated from the number of a's - it's obviously not the number of a's itself. – Pieter Witvoet Jul 11 '19 at 10:18

### Style

The indentation seems to be consistent, but the other whitespace isn't. Take just the first three lines:

        private static int  FindMaxInsert(string str)
{
int amount =0;


The double-space before the method name is unnecessary, but for consistency there should be a space after the = in the third line.

Some else lines have a blank line before them, and others don't. I would remove all of those blank lines.

Four blank lines before the return statement is definitely excessive.

amount is not an informative name. Amount of what?

            if (str.Contains("aaa"))
{
amount = -1;
}

else
{
... 59 lines ...
}

return amount;


If you use an early return in the first statement, you can lose a level of indentation from 90% of the method.

        Console.WriteLine("dog " + FindMaxInsert("dog"));
Console.WriteLine("aabab " + FindMaxInsert("aabab"));
Console.WriteLine("aa " + FindMaxInsert("aa"));
Console.WriteLine("a " + FindMaxInsert("a"));
Console.WriteLine("Empty " + FindMaxInsert(String.Empty));


Avoiding repetition is what for loops are for.

Tests aren't very useful if you don't compare the observed result to the expected result. What do you expect for each of these? (IMO it fails the last one).

Where's the test case for a substring of "aaa" giving an output of -1?

### Correctness

Here's a couple of test cases which this code fails:

Assert(FindMaxInsert("bbbbbb") == 14);
Assert(FindMaxInsert("babababa") == 6);


There's a lot of case analysis going on, and I'm not going to try to find the bug. Quicker to rewrite the whole thing using a simpler approach: consider pairs of non-a characters rather than triples of arbitrary characters.

• cant you explain "consider pairs of non-a characters rather than triples of arbitrary characters" ? – styx Jul 11 '19 at 9:05
• first, middle, last is a triple, and the code handles cases where they can be a or non-a. Think instead in terms of str[first] != 'a' and str[second] != 'a' where second is the smallest index greater than first for which this is true. – Peter Taylor Jul 11 '19 at 9:47

I don't code in C#, but I can clearly see the solution looks unreadable, and unnecessarily large. For the given problem there is a pattern. Take initial count = 2, for each character that is not 'a' add +2, for each character that is 'a' add -1.

S = aabab, count = 2

#count as you see characters

a  a  b  a  b
|  |  |  |  |
+2 -1 -1 +2 -1 +2 => 3

S = dog
+2 +2 +2 +2 => 8

S = babababa
+2 +2 -1 +2 -1 +2 -1 +2 -1 => 6

count = 2 + string.ToCharArray().Select(x => x == 'a' ? -1 : +2).ToArray().Sum();
//I've not tested this code


You just need one special case handling for aaa.

• great solution, but another special case(s) is an empty or null string – styx Jul 15 '19 at 5:45

### Verification Method

I'm counting 14 branches in your code. And still others have found edge cases that you don't cover. In order to find a good solution; one that covers all cases, we need a verification method. I believe Pieter's algorithm is very smart. But as with any solution, we need to be able to verify the results.

What better way than to brute-force all possible permutations and find the one that matches the specified pattern with the most number of insertions ..

I present a brute-force for the sole purpose of verifying any candidate solution to this problem. It is not optimized for performance, and it shouldn't be.

Tests

[TestMethod]
public void Verification()
{
// verify all possible permutations while debugging ..
var p1 = Helper.Permutate(null).OrderBy(x => x).ToArray();
var p2 = Helper.Permutate("").OrderBy(x => x).ToArray();
var p3 = Helper.Permutate(" ").OrderBy(x => x).ToArray();
var p4 = Helper.Permutate("dog").OrderBy(x => x).ToArray();
var p5 = Helper.Permutate("aabab").OrderBy(x => x).ToArray();
var p6 = Helper.Permutate("aa").ToArray();
var p7 = Helper.Permutate("baaaa").OrderBy(x => x).ToArray();

// verify the results
var max1 = Helper.GetMaxPossibleInsertions(null);      // -1
var max2 = Helper.GetMaxPossibleInsertions("");        //  2
var max3 = Helper.GetMaxPossibleInsertions(" ");       //  4
var max4 = Helper.GetMaxPossibleInsertions("dog");     //  8
var max5 = Helper.GetMaxPossibleInsertions("aabab");   //  3
var max6 = Helper.GetMaxPossibleInsertions("aa");      //  0
var max7 = Helper.GetMaxPossibleInsertions("baaaa");   // -1
}


Code

static class Helper
{
public static int GetMaxPossibleInsertions(string s = "", char c = 'a', int n = 3)
{
var max = -1;
var k = n - 1;
var pattern = new Regex(\$@"[{c}]{{{n}}}", RegexOptions.Compiled);
var permutations = Permutate(s, c, k).Where(p => !pattern.IsMatch(p)).ToArray();

max = permutations
.Select(p => p.Count(x => x == c) - s.Count(x => x == c))
.DefaultIfEmpty(max)
.Max();

return max;
}

public static IEnumerable<string> Permutate(string s = "", char c = 'a', int k = 2)
{
if (s == null)
yield break;
if (k < 1) k = 1;
var buffer = new StringBuilder(s);
foreach (var p in Permutate(buffer, c, k, 0, s.Length).Distinct()/*.OrderBy(x => x)*/)
{
yield return p;
}
}

static IEnumerable<string> Permutate(StringBuilder buffer, char c, int k, int m, int i)
{
// any intermediate result is a permutation
yield return buffer.ToString();
if (m < k)
{
// recursively find permutations with an inserted character
buffer.Insert(i, c);
foreach (var p in Permutate(buffer, c, k, m + 1, i))
{
yield return p;
}
buffer.Remove(i, 1);
}
if (i > 0)
{
// recursively find permutations with the insertion index moved back
foreach (var p in Permutate(buffer, c, k, 0, i - 1))
{
yield return p;
}
}
}
}