Leetcode discuss: 1371. Find the Longest Substring Containing Vowels in Even Counts

April 2, 2022

Here is the link.

C# | "aeiou" -> one integer, 5 bits, 32 variations | Warmup for Meta onsite

April 1, 2022
Introduction
I could not come out working ideas to solve the algorithm. I tried to solve it using sliding window to beat brute force O(N^2) solution, but it does not work. I was so nervous since I could not find a solution, there are five vowel chars, and I need to determine left pointer with matching vowel char count even or odd. Left pointer can be moved forward and backwrad two directions. So I chose to read votrubac solution, since I chose to go through algorithms based on his up-voted algorithms.

Idea to count all vowel chars "aeiou" | even 0, odd 1| "0001" meaning: a is odd, four chars in "eiou" even | Easy to play
Go through each char in given string once, and record the count in terms of 0 or 1 for five chars in "aeiou". If it is not found then set variable smallestIndex, apply substring comparison to any char not just vowel char. Do not skip non-vowel in comparison. Try yourself first, and then read my C# code, good luck!

Bit operation | C# | My bug written in my first practice
It is easy for me to write a C# bit operation algorithm. I checked all C# discuss post, none of them uses bit operation, so I decided to write one. But my code failed to return correct answer, given example, eleetminicoworoep, should return 13, but mine is 12. I could not figure out the reason, so I had to spend over 10 minutes to debug.

I should apply caclulation of matching vowel chars "vowel" even substring to any char, not just vowel. In other words, "leetminicowor", my search stops "leetminicowo", but skip last char 'r' since it is not vowel.

I quickly fixed the bug to limit scope of if statement in the following:

// update bitVariation if it is vowel char
if (index >= 0)  // if it is vowel char
{
    var current = 1 << index;  // left shift
    bitVariation ^= current; // double check XOR ^
}

Do you think that it is worth time for me to practice writing and debugging? I have ideas to solve the problem using bit operation, and I can write C# code but I stumbled a few places since I did not practice and took breaks over six months in 2021.

Places I stumbled in C#:

1. Declare C# bool[32] variable found, default value is false; but I was not sure until I debugged the code;
2. C# String.IndexOf(char) - syntax and usage, I have to depend on Visual Studio prompt to determine;
3. C# << left shift, only provide information once, vowels = "aeiou", I can quickly figure out how many bits to shift left;
4. C# XOR ^ - this is important XOR using module 2 as result, in other words 1^1 = 0, 1^0 = 1, 0^0 = 0;

The algorithm I chose to work on based on votrubac
I cannot find time to work on more than 200 submission last 12 months, so I have to figure out ways to compensate on this lack-of-hardwork. After carefully reviewing my options, I choose to work on a most reputable player and his up-voted algorithms, compared to mock interview, paid udemy FANG interview algorithm courses. Here is the idea. Welcome comments how to choose algorithms to work on to prepare Meta onsite. I have this idea after I reviewed 50 algorithms tag Facebook last six months.

The current algorithm is fourth algorithm below red circled algorthm in page 2.

The following C# code passes online judge.

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

namespace _1371_Find_longest_substring
{
    class Program
    {
        static void Main(string[] args)
        {
            var longest = FindTheLongestSubstring("eleetminicoworoep");
            Debug.Assert(longest == 13);
        }

        /// <summary>
        /// code review on April 1, 2022
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static int FindTheLongestSubstring(string s)
        {
            if (s == null || s.Length == 0)
                return 0; 

            var vowels = "aeiou";
            var smallestIndex = new int[32];
            var found = new bool[32]; // default - false           

            smallestIndex[0] = -1;
            found[0] = true;

            var bitVariation = 0; // five bit, each bit matches one of vowel char "aeiou"
            var length = s.Length;
            var maxSubstringLength = 0; 

            for (int i = 0; i < length; i++)
            {
                var c = s[i];
                var index = vowels.IndexOf(c);

                // update bitVariation if it is vowel char
                if (index >= 0)  // if it is vowel char
                {
                    var current = 1 << index;  // left shift
                    bitVariation ^= current; // double check XOR ^
                }

                // it applies to any char
                if (!found[bitVariation])
                {
                    smallestIndex[bitVariation] = i;
                    found[bitVariation] = true;
                }
                else
                {
                    maxSubstringLength = Math.Max(maxSubstringLength, i - smallestIndex[bitVariation]); 
                }                
            }

            return maxSubstringLength; 
        }
    }
}