July 4 2020 - 10:00 AM mock interview, find minimum substring containing given chars in the array

FindMinimumSubstring.cs

/*
Given an array of characters and a string, implement a function that finds the smallest substring containing all the characters in the array.

input:  arr = ['x','y','z'], str = "xyyzyzyx"

output: "zyx"

a - z 26 chars 
smallest - 
    return length or substring as well
propose: slide window
track all distinct chars

- iterate chars in the array twice - chars in the string 
case study:
"abbcbbccc" N
 ----------> "abc"   three chars   
               M
  |
     |            a 0, b 2, c1 still missing c  "abbc", length 4
    
time complexity: O(N), N is the length of string - argue that ...
space complexity: O(M) as well - count for each char, M is count of distinct chars
*/

using System;

// To execute C#, please define "static void Main" on a class
// named Solution.

class Solution
{
    static void Main(string[] args)
    {
        for (var i = 0; i < 5; i++)
        {
            Console.WriteLine("Hello, World");
        }
    }
    
    // contains all distinct chars
    // sliding window
    // use array to save those chars
    
    
    /*  'x' - 2, 'y' - 1, 'z' - 1


-identified concept for solution +

-correct explanation of sliding window +

-correctly analysed time and space complexity +

-handled wrong input edge case +

-wrong interpretation of problem text -

-good naming of variables +

-handled new input case +

-very good communication in while coding and explanation of flow of thought +

https://www.geeksforgeeks.org/tag/sliding-window/
https://www.geeksforgeeks.org/window-sliding-technique/

    */
    
    public string FindMinimmSubstring(string s, char[] given)
    {
        if(s == null || s.Length == 0)
            return "";
        
        var length = s.Length;
        
        var distinct = new int[26];
        
        foreach(var item in given)
        {
            distinct[item - 'a']++;  // increment one by one 
        }
        
        var minLength = length + 1; 
        var minSubstring = 0;  
        
        var left = 0;
        var index = 0; 
        var windowCount = new int[26];
        
        // slide window - left, index
        while(index < length)  // fall back to here 
        {
            var current = s[index];                       
            
            //qualified - compared to minimum one - move left point until it breaks
            if(qualified(windowCount, distinct))  //  
            {
                var currentWindow = index - left + 1; 
                if(currentWindow < minLength)
                {
                    minLength = currentWindow; 
                    minSubstring = left;                                        
                }
                
                // next step to move left point until it breaks
                var leftChar = s[left];
                windowCount[leftChar - 'a']--;
                left++; 
            }
            else
            {
                windowCount[current - 'a']++;  // take this outside of while 
                
                // index++
                index++; 
            }
        }
        
        
    }
}


/* 
Your previous Plain Text content is preserved below:

Welcome to your interviewing.io interview.

Once you and your partner have joined, a voice call will start automatically.

Use the language dropdown near the top right to select the language you would like to use.

You can run code by hitting the 'Run' button near the top left.

Enjoy your interview!
 */