Leetcode discuss: 1542. Find Longest Awesome Substring

April 12, 2022

Here is the link.

C# | Last position | Bit manipulation | Study code

April 12, 2022
Introduction
There is only one C# solution in discuss, and I chose to study it and wrote my own C# code.

Bit manipulation
From each integer n from 0 to 9, 2^n can be ranged from 1 to 512. So it is working solution to define masks array using those 10 numbers.

Case study: 76263
Given an integer 76263, longest substring 626 can be swapped into a palindrome.

Substring starting from index = 0, "7" can be mapped to prefixes[0] = 2^7 = 128. How to find a longest substring starting from index = 1 which can be swapped to a palindrome substring.

One of search is to find lastPosition defined as int[1024], here key is 128, lastPosition[128], if it is not defined or found, the default value of integer array is 0. Since maximum substring default value is 1, it is not a problem using default value 0 of lastPosition.

Another of search is to go through all possible masks - 1st to 9th bit, masks array index position from 0 to 9, XOR two values, one is prefixes[0] = 2&6 = 128, and look for last position of the mask value. If it is not found, then lastPosition array's lookup is 0, and then

lastPosition[prefixes[i] ^ mask] - i + 1

The above expression returns negative value, which does not matter since it will not be bigger than default value 1 of variable answer - maximum length of substring.

So "7", with all possible one extra digit, look for lastPosition with same odd and even count of string "70","71","72","73","74","75","76","77","78","79".

First tip | Use array for 10 bits = 1111111111 in binary form = 2^9 + 2^8 + ...+ 2^0 < 2^10 = 1024 | Compare to use HashMap
It is hard level algorithm. Most of important is to design a working solution. Using array compared to HashMap on this algorithm definitely makes it easy to write a working solution.

Last position vs first position | Luck or smartness | I do not know
I chose to first position, but I came cross a bug and I could not fix it. My design and the algorithm failed one test case: 9498331. Here is my C# practice with failed test case.

I learned to write using last position by studying discuss section C# code. I do not know how to advance myself in such short time to prepare for May Meta onsite.

The following code passes online judge.

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

namespace _1542_study_code
{
    class Program
    {
        static void Main(string[] args)
        {   
            var max = LongestAwesome("9498331");
            Debug.Assert(max == 3);

            var max2 = LongestAwesome("30003");
            Debug.Assert(max2 == 5);

            // 76263 - 30003
            var max3 = LongestAwesome("76263");
            Debug.Assert(max3 == 3);
        }

        /// <summary>
        /// study code:
        /// https://leetcode.com/problems/find-longest-awesome-substring/discuss/952409/C-Bit-Manipulation
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static int LongestAwesome(string s)
        {            
            var masks = new int[] { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };

            var length = s.Length;
            // calculate prefixes
            var prefixes = new int[length + 1];

            for (var i = 1; i <= length; i++)
            {
                // XOR - 1 or 0, even or odd count
                prefixes[i] = prefixes[i - 1] ^ masks[s[i - 1] - '0'];
            }

            // calculate last indexes of prefixes
            // 1024 - what for? 2^10 = 1024, 0 - 9, 2^0 = 1, ..., 2^9 = 512 
            var lastPosition = new int[1024];

            for (var i = 0; i < s.Length; i++)
            {
                lastPosition[prefixes[i + 1]] = i;
            }

            var answer = 1;
            // check max length between last index (+ any variations(10)) and current index
            // I failed in my practice since I chose to work on previous position - this makes buggy code
            for (var i = 0; i < length; i++)
            {
                answer = Math.Max(answer, lastPosition[prefixes[i]] - i + 1);

                foreach (var mask in masks)
                {
                    answer = Math.Max(answer, lastPosition[prefixes[i] ^ mask] - i + 1);
                }
            }

            return answer;
        }
    }
}