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

MUTABLE AND IMMUTABLE OBJECTS IN PYTHON AND THEIR MEMORY MANAGEMENT

Everything in Python is an object. There are two types of objects in Python Mutable Immutable Mutable objects are those whose value can be changed after their creation. An example of it is a  list. Immutable objects are those whose value cannot be changed after their creation. A well-known example of this is a tuple. Mutable objects: lists, sets, dictionaries Immutable objects: Tuples, integers, floats, strings, frozen sets Before going deep into this topic, we should know about the  id() function in Python. id() function in python: This function returns the identity of an object. This is guaranteed to be unique and constant for an object. The id of an object is created when the object is created. See below for examples. example1 :                                                          ...
Post a Comment
Read more