Leetcode discuss: 1542. Find Longest Awesome Substring

April 12, 2022

Here is the link. 

C# | First position | Bit manipulation | Failed: "9498331" | Lessons learned

April 12, 2022
Introduction
It is a hard level algorithm. I chose to work on it, since I just did solve a similar bit manipulation algorithm 1371. Find the Longest Substring Containing Vowels in Even Counts based on discuss post by votrubac. I chose to work on first position of bit manipulation, and I came cross this failed test case "9498331". I could not solve the issue, and I just could not believe that how others solve the problem but no warning on this first position idea and its bugg issue.

Brute force solution | O(N^2)
It takes O(N^2) to find all substrings, and then it can be calculated to maximum substring to be swapped to a palindrome.

Optimal solution | Hashmap to record count of digits
It is easy to come out the design to use 10 bits to represent 0 to 9 10 digits, even or odd count using 0 or 1 to represent.

Case study | "9498331" | Should return 3, not 4

The following code failed test case: 78 / 153 test cases passed.
Input:
"9498331"
Output: 4
Should be: 3

Lesson learned:
Analysis:
949833
94 - remove 9, so, 4 maps to a number 1<< 4 = 2^4 = 16.
949833 - remove 8, 94933 maps to a number 1 << 4 = 2^4 = 16
first position with 16's index = 1, and the current positon with 16's index = 5, so the answer is 4, but "9833" can not be a palindrome by the option to remove one char.

There are more than two issues in my design using those 10 bits mask to map 0 to 9 10 digits. It took me hours to figure out what is wrong, and how to address the issues.

Faulty design | Save substring with all possible one extra digit into HashMap
I just gave it a quick try without strictly proof that it should work. I even save extra key into HashMap to pad at the end one more digit - any digit from 0 to 9.

I chose to use first position, and then handle extra digit case. It is not easy to figure out so many things in such a short time. Just be patient. Learn from those failed submissions and those failed test cases, and I think that the failures should be best teacher for me. To prepare for Mata onsite in May 2022, I should try 10 hard level algorithms, and learn from all those mistakes in practice. Here is my discuss post related to Meta onsite 30 day preparation.

I should work on last position instead.

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

namespace _1542_find_longest_awesome_substring
{
    class Program
    {
        static void Main(string[] args)
        {
            //var maximumLength = LongestAwesome("3242415");
            //Debug.Assert(maximumLength == 5);

            var max = LongestAwesome("9498331");
            Debug.Assert(max == 3);
        }

        /// <summary>
        /// April 8, 2022
        /// Brute force solution O(N^2) 
        /// find all substrings and then check if it is an awesome substring
        /// Optimal solution should be O(N), go through the array once, and then 
        /// record all digits count in terms of even or odd, using one integer 10 bits 
        /// to contain all 10 bits - left to right, 0 - 9
        /// 
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static int LongestAwesome(string s)
        {
            if (s == null || s.Length == 0)
            {
                return 0;
            }
            
            var map = new Dictionary<int, int>();            

            map.Add(0, -1); //

            var length = s.Length;
            var bitsForDigits = 0;
            var maxLength = 0;

            // 0 ^ 0 = 0
            // 0 ^ 1 = 1
            // 1 ^ 1 = 1  // xor - determine odd or even in each bit
            for (int i = 0; i < length; i++)
            {
                var digit = s[i] - '0';
                bitsForDigits ^= 1 << digit;

                if (!map.ContainsKey(bitsForDigits))
                {
                    map.Add(bitsForDigits, i);
                }
                else
                {
                     maxLength = Math.Max(maxLength, i - map[bitsForDigits]);
                }
                  
                // search odd matching 
                // brute force all digits with 1 - at most 10 cases
                for (int shift = 0; shift <= 9; shift++)
                {
                    // mask one bit
                    if ((bitsForDigits & (1 << shift)) == 0)
                    {
                        continue;
                    }

                    var key = bitsForDigits ^ (1 << shift);  // remove one digit

                    if (!map.ContainsKey(key))
                    {
                        map.Add(key, i);
                    }
                    else
                    {
                        // 949833, remove 4, 99833, but 8's count is odd 
                        //if (key == 0)  // make sure that all digits have even count
                        {
                            maxLength = Math.Max(maxLength, i - map[key]);
                        }
                    }
                }
            }

            return maxLength;
        }
    }
}