using System;

using System.Text;

​

public class Program

{

    public static void Main()

    {

        var input = "aba";

        var result = IsPerfect(input);

        Console.WriteLine("IsPerfect({0}) = {1}", input, result);

        var input2 = "aaca";

        var result2 = PerfectIndex(input2);

        Console.WriteLine("PerfectIndex({0}) = {1}", input2, result2);

        var input3 = "aaacb";

        var result3 = PerfectIndexes(input3);

        Console.WriteLine("PerfectIndexes({0}) = {1},{2}", input3, result3[0], result3[1]);

    }

    // O(n/2) -> O(n)

    private static bool IsPerfect(string input)

    {

        for (int i = 0; i < input.Length/2; i++)

        {

            if (input[i] != input[input.Length - i - 1])

            {

                return false;

            }

        }

        return true;

    }

    // O(n) * O(IsPerfect(n)) -> O(n^2)

    private static int PerfectIndex(string input)

    {

        var modifiedInput = new StringBuilder(input);

        int index = 0;

        while (index < input.Length)

        {

            var removedChar = input[index];

            modifiedInput.Remove(index, 1);

            if (IsPerfect(modifiedInput.ToString()))

            {

                return index;

            }

            modifiedInput.Insert(index, removedChar);

            index++;

        }

        return -1;

    }

    // O(n * O(PerfectIndex(n)) -> O(n^3)

    private static int[] PerfectIndexes(string input)

    {

        var modifiedInput = new StringBuilder(input);

        int index = 0;

        while (index < input.Length)

        {

            var removedChar = input[index];

            modifiedInput.Remove(index, 1);

            int perfectIndex = PerfectIndex(modifiedInput.ToString());

            if (perfectIndex != -1)

            {

                if (perfectIndex >= index)

                {

                    perfectIndex++; 

                }

                return new int[]{index, perfectIndex};

            }

            modifiedInput.Insert(index, removedChar);

            index++;

        }           

        return null;

    }

}