Algorithm : Longest Substring Without Repeating Characters

    Algorithm : Longest Substring Without Repeating Characters

Problem Statement: Given a string, find the length of the longest substring without repeating characters.  This question can be found in leetcode #3. 
   Example: if the input string is "sreenath", then the output should be: 5 
   Reason\Explanation: 
  • sre - First three characters, until the next e.  - 3
  • re. -  we move the next substring which is re until  - 2
  • since no words can be formed using starting with ee. -0 
  • enath   -  with no repeating characters. - 5 
   As you can see that the maximum number of characters is 5. 


    Logic:

    Sliding Window Technique:
    
    We have a window just like how you have a Window at home, if you want to open the window fully,       you basically slide the window to the fullest. If you have to slide so that you don't open completely, you have a choice how much you want to slide the window to. 

    Typical scenario of a sliding window technique will be: 
    • You have a left and right pointer, both set to index 0
    • You slide the window by incrementing the right pointer until a case is false. 
    • You slide the window by incrementing the left pointer until a case is true. 
    • In the above scenario, you slide(or increment ) the right pointer, till there are no duplicates.
    • You slide or (increment) the left pointer, when there are duplicates. 
    • At each step you find the maximum number(longest substring), - in the above scenario, when the case is true.        

static int LengthOfSubString(string s)
{
// Start of the window.
int startWindow = 0;
// End of the window
int endWindow = 0;
//Max Length at each step.
int maxLength = 0;
//HashSet for O(1) - Insert, Delete and search time.
//This is used to insert the characters along the way and remove the
//characters when the duplicates are found.
HashSet<Char> set = new HashSet<char>();
while(endWindow < s.Length)
{
if (!set.Contains(s[endWindow]))
{
set.Add(s[endWindow]);
maxLength = Math.Max(maxLength, endWindow - startWindow + 1);
endWindow++;
}
else
{
set.Remove(s[startWindow++]);
}
}

return maxLength;
}

static void Main(string[] args)
{
Console.WriteLine("Hello World!");

Console.WriteLine(LengthOfSubString("sreenath"));
}

//o/p: 5

Comments

Post a Comment

Popular posts from this blog

Knowing too much is bad(in the world of OOP)

In real life, we have heard experts say that knowing too much or sometimes doing too much is bad.  This is the same in the world of Object Oriented Programming, this is called as God Object. The God object is an example of anti-pattern(code that is difficult to understand, refactor and maintain) and a code smell.  We have heard of Single-responsibility Principle(which is "S" in the SOLID principles). The SRP states that each class should have only responsibility and therefore has only one reason to change.  Whenever a code is written, make sure that the class does only one thing. You can refer to the God Object here at wikipedia which gives a brief description: https://en.wikipedia.org/wiki/God_object
Read more

Reverse a LinkedList Algorithm

Reversing a Linked List Problem Statement:  Reverse a Linked List.  Given a Linked List of Nodes  :  1->2->3->4->5->6 , reverse it so that the output is 6->5->4->3->2->1 My Approach:  For this approach, we cannot the same LinkedListNode since it would point to the same memory location. In the above example, 1 should point to null of the new List. 2 which is 1.next (original) should point to 1 of the new List. 3 which is 2.next (original) should point to 2 of the new List. 4 which is 3.next (original) should point to 3 of the new List. 5 which is 4.next (original) should point to 4 of the new List. 6 which is 5.next (original) should point to 5 of the new List. This is where our logic ends. 1) LinkedListNode Class  This class has 2 Components of a Singly Linked List.  Value of the node Pointer to the Next Node.           public class LinkedListNode ...
Read more

DateTime.Now in C#

DateTime Class is used to get the various possibilities that can be included within a day, month or a year. I am going to discuss about some functionalities of DateTime.Now here. For example: To get the current date and time, use DateTime.Now which gives us 6/24/2009 9:45:00 AM DateTime.Now has 5 important functions to get date and time in different formats. 1) DateTime.Now.ToLongDateString() - Displays in the format "Wednesday, June 24, 2009." 2) DateTime.Now.ToLongTimeString() - Displays in the format "12:00:00 AM. " 3) DateTime.Now.ToShortDateString() - Displays in the format "6/24/2009" 4) DateTime.Now.ToShortTimeString() - Displays in the format "12:00 AM" 5) DateTime.Now.ToString("Format") - This method accepts different formats. The formats can be obtained from GetDateTimeFormats() method of DateTime.Now and has 133 different formats that anyone can think of while displaying Date and Time. For example: DateTime.Now.ToString(...
Read more