Hacerrank world codesprint #5 - short palindrome - need to review the code later.

shortPalindrome.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ShortPalindrome
{
    class Program
    {
        /*
         * https://www.hackerrank.com/contests/world-codesprint-5/challenges/short-palindrome
         */
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            //string s = "abbaab"; 

            Console.WriteLine(getShortPalindrome(s, GetAlphabetic(s)));
        }

        public static void testFunc()
        {
            int[] test1 = GetAlphabetic("aaab");

            string test2 = Convert01Strings("abcdefac", 'a', 'c');

            // test case 1: "011001"  - 4

            //    long count = countingPalindromes("0000001", true);
            //    count += countingPalindromes("00000011", false); 
        }

        public static int[] GetAlphabetic(string s)
        {
            int[] res = new int[26];

            if (s == null || s.Length == 0)
                return res;

            string alphabeticNumbers = "abcdefghijklmnopqrstuvwxyz";
            int   TOTAL = 26;
            int[] countAlphabetic = new int[TOTAL];


            char[] alphabeticChars = alphabeticNumbers.ToArray();

            for (int i = 0; i < s.Length; i++)
            {
                int index = s[i] - 'a';
                countAlphabetic[index]++;
            }

            return countAlphabetic;
        }

        /*
         * Calculate short palindrome 
         * - big issues:
         * 1. time out
         * 2. wrong answer
         * 3. run time issue
         * 
         */
        public static long getShortPalindrome(string s, int[] input)
        {
            long output = 0;
            int SIZE = 26;

            long moduleValue = ((long)Math.Pow(10, 9) + 7);

            for (int i = 0; i < SIZE; i++)
            {
                int current = input[i];

                long product = 1;
                if (current >= 4)
                {
                    int index = 0;
                    while (index <= 3)
                    {
                        product = (product * (current - index)) % moduleValue;
                        index++;
                    }

                    product /= 24;
                    output += product % moduleValue;
                }
            }

            var dict = new Dictionary<string, long>();
            var dict2 = new Dictionary<string, long>();

            for (int i = 0; i < SIZE; i++)
            {
                for (int j = i + 1; j < SIZE; j++)
                {
                    int val1 = input[i];
                    int val2 = input[j];

                    if (val1 < 2)
                    {
                        break;
                    }

                    if (val2 < 2)
                    {
                        continue;
                    }

                    char char_A = (char)(i + 'a');  // bug001 - not val1, should be i, 
                    char char_B = (char)(j + 'a');  // bug002 - not val2, should be j

                    string s1 = Convert01Strings(s, char_A, char_B);

                    if (dict.ContainsKey(s1))
                    {
                        output += dict[s1] % moduleValue;
                    }
                    else
                    {
                        output += CalculatePalindromes(s1, true, dict2) % moduleValue;
                        output += CalculatePalindromes(s1, false, dict2) % moduleValue;
                    }
                }
            }

            return output;
        }

        /*
         * using 0 and 1 to construct the string
         * 1001
         * 0110 
         * 
         * There are 26 chars in alphabetic string, any two combination is 26*25/2*1 > 250
         * Instead, using 0 and 1 to stand for two distinct characters. 
         * for example, abab
         * 0101
         * So, we can conclude one thing:
         * ababa
         * 01010
         * or 
         * 10101
         * So, use memorization, 01010 and 10101 should be same key 
         * See if this can solve time out issues - July 25, 2016
         * 
         * reverse of string should be same key
         */
        public static string Convert01Strings(string s, char char0, char char1)
        {
            var output = new StringBuilder();

            if (s == null || s.Length == 0)
            {
                return "";
            }

            var data = new char[2] { char0, char1 };

            for (int i = 0; i < s.Length; i++)
            {
                char index = s[i];

                if (Array.IndexOf(data, index) != -1)
                {
                    if (index - char0 == 0)
                    {
                        output.Append('0');
                    }
                    else
                    {
                        output.Append('1');
                    }
                }
            }

            return output.ToString();
        }


        /*
         * use two loops
         * 
         * get 0110 pairs
         * get 1001 paris 
         * 
         * Think about DP solution - dynamic programming - not working, too complicate
         * 
         * brute force solution:
         * 0 - start char, end char, and then, count how many possibilities
         * Go through O(n*n) case, for any two 0 in pseudo string, check in-between
         * 
         * For example:
         * 001010110
         * 
         * The above case, there are 5 '0', 
         * position of '0' is 0, 1, 3, 5, 8, 
         * So, any two '0' combinations are 5*4/2*1 = 10
         * 
         * A: 0, 1, in between, there is no chars, n/a
         * B: 0, 3, 2 chars in between - "01", count how many '1' in the substring, only 1. 
         * C: 0, 5, 4 chars in between - "0101", two one inside, so how many combination
         * of 11, only 1 choice. 
         * D: 0, 8, 7 chars in-between - "0101011", four one's in the substring, how many combination - 4*3/2 = 6 choices
         */
        public static long CalculatePalindromes(string s, bool first0, Dictionary<string, long> dict)
        {
            if (s == null || s.Length == 0)
            {
                return 0;
            }

            int  length = s.Length;
            char compare = first0 ? '0' : '1';
            char counting = first0 ? '1' : '0';

            long count = 0;
            long moduleValue = ((long)Math.Pow(10, 9) + 7);

            for (int i = 0; i < length; i++)
            {
                for (int j = i + 3; j < length; j++)
                {
                    char first = s[i];
                    bool firstOne = (first - compare) == 0;

                    if (!firstOne)
                    {
                        break;
                    }

                    char second = s[j];
                    bool secondOne = (second - compare) == 0;

                    if (secondOne)
                    {
                        // count how many 1 in-between
                        string s1 = s.Substring(i, j - i);

                        long ones = 0;
                        if (dict.ContainsKey(s1))
                        {
                            ones = dict[s1];
                        }
                        else
                        {
                            ones = CountTotal(s1, counting);
                            dict[s1] = ones;
                        }

                        count += (ones * (ones - 1) / 2) % moduleValue;
                    }
                }
            }

            return count % moduleValue;
        }
        
        private static long CountTotal(string s, char compare)
        {
            if (s == null || s.Length == 0)
            {
                return 0;
            }

            long count = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == compare)
                {
                    count++;
                }
            }

            return count;
        }
    }
}