Skip to main content

LENGTH OF LONGEST VALID SUBSTRING

GIVEN A STRING OF PARENTHESIS, PRINT THE LENGTH OF THE LONGEST BALANCED SUBSTRING.

FOR EXAMPLE: GIVEN, 
            1. ()() ---> 4 
            2. ()())()()() ---> 6 
Brute Force Approach:  It is to find all the substrings, and check whether they are balanced or not, and simultaneously updating the result if we find a larger valid substring than the previous one. But, this takes the time of O(N^3), since finding all the substrings take O(N^2), and for each substring, to find whether it is a valid substring, it takes a time of O(N), so this constitutes a total of O(N^3). 

USING STACK: In this approach, we will maintain a stack to store the indices of the traversed opening brackets i.e., '('. [YOU WILL KNOW THE REASON SOON, KEEP READING THE POST]. 
And a variable res, to store the length of the longest substring known till now. 

ALGORITHM: 
**THE TOP OF THE STACK WILL BE USED TO COMPUTE THE LENGTH OF THE VALID SUBSTRING. 

 1. Initiate the stack with -1, and res with 0. 
 2. Start traversing the string. 
 3. If it is opening bracket '(', push the index into the stack. 
 4. If it is closing bracket ')': 
       1. Then pop the element from the stack. 
       2. If the stack is not empty: 
               Then the difference between the current index and the top of the stack will give you the length of the substring that is balanced with the closed bracket at the current index. If it is greater than the res, then update res with the difference. 
           If the stack is empty: 
               This means that there is no opening bracket to the left of the encountered closing bracket. So, push the current index into the stack which will be used to find the length of the next valid substring. 

 IF YOU DO NOT UNDERSTAND THIS ALGO, THEN GRAB A BOOK AND PEN, APPLY THIS ALGORITHM TO '()))()()(). I AM SURE YOU WILL UNDERSTAND THE LOGIC BEHIND THIS ALGORITHM. 

 CODE:
Labels:

Comments

Post a Comment

Popular posts from this blog

CHATBOT WITH SPEECH RECOGNITION AND PYTTSX3 USING PYTHON

NOTE: VIEW THIS POST IN DESKTOP SITE FOR THE BEST EXPERIENCE Hello guys. Welcome to my blog. Here I will explain to you how to create a chatbot that has speech as it’s both input and also output. So, let us get started. In this tutorial, I am using some of the libraries in Python like SpeechRecognition, Pyaudio, Chatterbot et cetera. I am going to explain to you how to install these libraries and work with them one by one separately and at last how to integrate them. SPEECH TO TEXT At first, you have to install the Speech Recognition library. You should not use the Python3.7 version because it does not support speech recognition. I am using a 3.6 version for this tutorial. Now, you should install the speech recognition library from the command prompt. Use the following command. pip3.6 install SpeechRecognition Now, you should install PyAudio. First, you have to find the version of your Python and also the configuration of your machine. Open your cmd and type p...
3 comments
Read more

RECOGNITION OF HANDWRITTEN DIGITS(MNIST DATA) PART ONE USING PYTORCH

HELLO GUYS, IN THIS BLOG POST I WANT TO SHOW THE BASIC INTRO TO IDENTIFICATION OF HANDWRITTEN DIGITS USING PYTORCH MNIST DATA. MNIST DATA IS THE COLLECTION OF HANDWRITTEN DIGITS. MNIST CONTAINS 70,000 HANDWRITTEN DIGITS, 60,000 FOR TRAINING AND REMAINING 10,000 ARE FOR TESTING.  THE  IMAGES ARE GRAYSCALE AND 28x28 PIXELS. WE CAN DOWNLOAD THE DATASET USING THE CODE BELOW. Here, the parameters batch_size is kept to 64 so that the training images are grouped into 64 each and shuffle is kept to TRUE, such that each time we run the code it shuffles the data and returns an iterable with new groups of batch_size. As the trainloader is iterable, we are iterating through it and collecting the first batch of images and it's corresponding labels into images and labels respectively. Now, run the above code and see the output. you will see something like this. torch.Size([64, 1, 28, 28]) torch.Size([64])  It shows that there are 64 images with grayscale an...
Post a Comment
Read more