Maximum character insertion

Question

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"

Comments explanation:

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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