Validate string coupons which could be combo of other valid coupons

This is code question asked by Amazon on Hacker Rank. Please help to resolve it.

Code Question At Amazon's annual sale, employees are tasked with generating valid discount coupons for loyal customers. However, there are some used/invalid coupons in the mix, and the challenge in this task is to determine whether a given discount coupon is valid or not.

The validity of a discount coupon is determined as follows:

1. An empty discount coupon is valid.
2. If a discount coupon A is valid, then a discount coupon C made by adding one character x to both the beginning of A and the end of A is also valid (i.e the discount coupon C = xAx is valid).
3. If two discount coupons A and Bare valid, then the concatenation of B and A is also valid (i.e the coupons AB and BA are both valid).

Given n discount coupons, each coupon consisting of only lowercase English characters, where the i-th discount coupon is denoted discounts[i], determine if each discount coupon is valid or not. A valid coupon is denoted by 1 in the answer array while an invalid coupon is denoted by 0.

Example discounts = ['tabba'; 'abca']

Check if this coupon code can be constructed within the rules of a valid coupon. Checking 'abba': • The empty string is valid per the first rule. • Under the second rule, the same character can be added to the beginning and end of a valid coupon code. Add 'b' to the beginning and end of the empty string to have 'bb', a valid code. • Using the same rule, 'a' is added to the beginning and end of the 'bb' coupon string. Again, the string is valid.

The string is valid, so the answer array is 1.

Checking 'abca': • Using rule 2, a letter can be added to both ends of a string without altering its validity. The 'a' added to the beginning and end of 'bc' does not change its validity. • The remaining string 'Ix', is not valid. There is no rule allowing the addition of different characters to the ends of a string.

Since the string is invalid, append 0 to the answer array. There are no more strings to test, so return [1,0]

Function Description

Complete the function find ValidDiscountCoupons in the editor below.

find ValidDiscountCoupons has the following parameter: string discounts[n]: the discount coupons to validate

Returns int[n]: each element i is 1 if the coupon discounts[il is valid and 0 otherwise

My solution (only partially correct):

    public static List<int> findValidDiscountCoupons(List<string> discounts)
    {
        var r = new List<int>(); // result
        foreach (var s in discounts)
        {
            if (s == "")
                r.Add(1);
            else if (s.Length == 1)
                r.Add(0);
            else
            {
                if (isAllCharCountEven(s) && areCharPairsValid(s))
                    r.Add(1);
                else
                    r.Add(0);
            }
        }

        return r;
    }

    public static bool areCharPairsValid(string s)
    {
        char[] a = s.ToCharArray();

        int y = a.Length;

        for (int x = 0; x < y; x++)
        {
            if (x + 1 < y && a[x] == a[x + 1])
            {
                // two valid characteres together
                x++;
            }
            else if (a[x] == a[y - 1])
            {
                // chars at the front and the end of array match
                y--;
            }
            else
            {
                return false;
            }
        }

        return true;
    }

    public static bool isAllCharCountEven(string s)
    {
        while (s.Length > 0)
        {
            int count = 0;
            for (int j = 0; j < s.Length; j++)
            {
                if (s[0] == s[j])
                {
                    count++;
                }
            }

            if (count % 2 != 0)
                return false;

            s = s.Replace(s[0].ToString(), string.Empty);
        }

        return true;
    }

https://github.com/sam-klok/DiscountCouponesValidation

Solution 1:

    private static bool _IsValid(string input)
    {
        //When input is empty
        if (String.IsNullOrEmpty(input))
        {
            return true;
        }

        //When input is only one character
        if (input.Length == 1)
        {
            return false;
        }

        char[] inputChar = input.ToCharArray();

        //When input is two same characters
        if (input.Length == 2)
        {
            if (inputChar[0] == inputChar[1])
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        //When input is > two character
        if (input.Length > 2)
        {
            //Split into two inputs
            for (int i = input.Length - 1; i > 0; i--)
            {
                if (inputChar[0] == inputChar[i])
                {
                    //Get first part
                    bool first = _IsValid(input[1..i]);

                    //Get second part
                    bool second = true;
                    if (first && i + 1 != input.Length)
                    {
                        second = _IsValid(input[(i + 1)..input.Length]);
                    }

                    return first && second;
                }
            }
        }
        return false;
  }