CodeWIthNeelima

TRICK TO REDUCE TIME COMPLEXITY USING HASH CONCEPT [DICTIONARY] Today, I learned a new way to know the indices of characters in a string.  Example: If you have a string containing alphabets, and while doing some problem, inside a for loop, you need to access a particular alphabet's index in that string , you will definitely use string.index(k) function, where 'k' represents alphabet. But, it takes O(N) time, as it searches the whole string and returns the index as soon as it finds that particular alphabet. As we are performing this operation inside another for loop , this logic takes O(N^2) for implementation. But, we can know the index of that particular alphabet in O(1) time. Let us see HOW? Here, in the above code, we use the dictionary to store the alphabets in a string as keys and the corresponding indices as values. As the dictionary uses the hash table concept for accessing the value of a particular key, it takes a constant time,  i.e., O(1).  So, now if we use t...

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....