# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3.9.6 64-bit
#     language: python
#     name: python396jvsc74a57bd0b0fa6594d8f4cbf19f97940f81e996739fb7646882a419484c72d19e05852a7e
# ---

# # String Data Structure
# ## &copy;  [<NAME>](<EMAIL>) ##
# ### Industrial and Enterprise Systems Engineering, The Grainger College of Engineering,  UIUC ###
#
# <hr style="border:2px solid blue"> </hr>
#
# ## 1. Check if a given string is a valid number (Integer or Floating Point) | SET 2 (Regular Expression approach)

# +
// Java program to check whether given string
// is a valid integer number using regex

import java.util.regex.Pattern;
import.java.util.regex.Matcher;

class GFG
{
    public static void main(String[] args)
    {
        String input1 = "abc";
        String input2 = "1234";

        // regular expression for an integer
        String regex = "[+-]?[0-9][0-9]*";

        // compile regex
        Pattern p = Pattern.compile(regex);

        // Create a matcher that will match input 1 against regex
        Matcher m = p.matcher(input1);

        // If match found and equal to input1
        if(m.find() && m.group().equals(input1))
            System.out.println(input1 + " is a valid integer")
        else
            System.out.println(input1 + " is not a valid integer")
        
        // Creates a matcher that will match input2 against regex
        m = p.matcher(input2);
          
        // If match found and equal to input2
        if(m.find() && m.group().equals(input2))
                System.out.println(input2 + " is a valid integer number");    
        else
            System.out.println(input2 + " is not a valid integer number");
    }
}

class GFG1
{
    public static void main(String[] args)
    {
        String input1 = "10e5.4";
        String input2 = "2e10";

        String regex = "[+-]?[0-9]+(\\.[0-9]+)?([Ee][+-]?[0-9]+)?";

        Pattern p = Pattern.compile(regex);
        Matcher m = p.matcher(input1);
        if (m.find() && m.group().equals(input1))
            System.out.println(input1 + " is a valid floating number");
        else
            System.out.println(input1 + " is not a valid floating number");
        m = p.matcher(input2);
        if (m.find() && m.group().equals(input2))
            System.out.println(input2 + " is a valid floating number");
        else
            System.out.println(input2 + " is not a valid floating number");
    }
}

# -

# ## 2. Minimum Window Substring
#
# Given two strings `s` and `t`, return the minimum window in `s` which will contain all the characters in `t`. If there is no such window in `s` that covers all characters in `t`, return the empty string `""`.

# +
from collections import Counter

def minWindow(s, t):
    # count dictionary to store unique characters
    dict_t = Counter(t)

    # interger variable to store the count of the unique characters of s that are also in t
    formed = 0

    # desired length of the window
    required = len(dict_t)

    # tuple to store (window lenght, left, right pointers)
    ans = float("inf"), None, None

    # left and right pointers
    l, r = 0, 0

    # list that stores the (index, char) of s that are also present in t
    filtered_s = []

    # store the count of the characters, as we go through filtered_s
    window_counts = {}

    # go through index i and character char. If char is present in dict_t, append it to filtered_s
    for i, char in enumerate(s):
        if char in dict_t:
            filtered_s.append((i, char))
    
    # while right pointer has not reached the end
    while r<len(filtered_s):
        # get the character stored in filtered_s's r index
        character = filtered_s[r][1]
        # increment its count in window_counts
        window_counts[character] = window_counts.get(character, 0) + 1
        # if this count matches that of dict_t, increment formed by 1
        if window_counts[character] == dict_t[character]:
            formed += 1

        # try and contract the window till the point where it ceases to be desirable
        while l<=r and formed == required:
            # get the character stored in l index of filtered_s
            character = filtered_s[l][1]

            # get the left and right indices of s
            start = filtered_s[l][0]
            end = filtered_s[r][0]
            # if the window length is less than what's stored at ans[0], update it
            if end-start+1 < ans[0]:
                ans = (end-start+1, start, end)
            # this character is no longer a part of the window
            window_counts[character] -= 1
            if window_counts[character] < dict_t[character]:
                formed -= 1
            # move left pointer ahead to get a new window
            l += 1
        # keep expanding the window once we are done contracting
        r += 1
    return "" if ans[0] == float("inf") else s[ans[1]: ans[2]+ 1]
s = "ABAACBAB"
t = "ACB"
minWindow(s, t)
# -

# ## 3. Smallest window that contains all characters of string itself
#
# Given a string, find the smallest window length with all distinct characters of the given string. For eg. str = “aabcbcdbca”, then the result would be 4 as of the smallest window will be “dbca” .

# +
from collections import defaultdict

def SubString(strr):
    # get the length of the input string
    n  = len(strr)
    # if it is 1 or 0, return the input string
    if n <= 1:
        return strr

    # variable to store the count of the distinct characters of string, as we go through it
    count = 0
    # store the desired count of the distinct characters of the input string
    dist_count = len(set([x for x in strr]))

    # start index of the substring
    start = 0
    # length of the final substring
    min_len = 0
    # dictionary to store the count of the characters in the input string
    curr_count = defaultdict(lambda: 0)

    # go through the characteres in input string 
    for j in range(n):
        # increment its count by 1 in curr_count
        curr_count[strr[j]] += 1
        # if distinct character found
        if curr_count[strr[j]] == 1:
            # increment the count of 1
            count += 1
        
        # if count is equal to the desired count
        if count == dist_count:
            # reduce the length of the window by removing useless characters that are occuring more no. of times
            while curr_count[strr[j]] > 1:
                if curr_count[strr[j]]>1:
                    curr_count[strr[j]] -= 1
                start += 1
            
            # update the current window length
            len_window = j - start + 1
            # if it is less than min_len, update it and the start_index of the final substring
            if min_len>len_window:
                min_len = len_window
                start_index = start
    return str(strr[start_index: start_index+min_len])

# Driver code
if __name__ == '__main__':
 
    print("Smallest window containing "
          "all distinct characters is: {}".format(
              findSubString("aabcbcdbca")))


# -

# ## 4. Number of substrings of a string
#
# Find total number of non-empty substrings of a string with N characters. 

# +
def countNonEmptySubString(string):
    n = len(string)
    return int(n * (n+1)/2)

s = "abcde"
print(countNonEmptySubString(s))
# -

# ## 5. Print all distinct characters of a string in order 
#
# Given a string, find the all distinct (or non-repeating characters) in it. The distinct characters should be printed in same order as they appear in input string.

# +
MAX_CHAR = 256

def printDistinct(string):
    n = len(string)

    # count stores the count of the character 'x'. 
    # If x is not present in string, count will be 0.
    count = [0 for i in range(MAX_CHAR)]

    # index stores the index of the character 'x' in string. If 'x' is not present or 'x' is more than once,
    # then it will store a value that is not a valid index in input string
    index = [n for i in range(MAX_CHAR)]

    # Traverse the string
    for i in range(n):
        # Get the unicode value of the character stored at index 'i' in string
        x = ord(string[i])
        # Increment the count
        count[x] += 1

        # if it's the first occurence of x or x is not space, store the index of string of x in 'index'
        if count[x] == 1 and x != " ":
            index[x] = i
        
        # if x occurs more than once, remove it
        if count[x] == 2:
            index[x] = n
    
    # sort the index
    index = sorted(index)

    for i in range(MAX_CHAR):
        if index[i]==n:
            break
        print(string[index[i]], end = '')

# Driver code
Str = "GeeksforGeeks"
printDistinct(Str)
# -

# ## 6. Printing Longest Common Subsequence | Set 2 (Printing All)
#
# Given two sequences, print all longest subsequence present in both of them.

# +
# maximum length of L
N = 100
# L stores the length of the common subsequences of x and y. x is in the row and y is in the column
L = [[0 for i in range(N)] for i in range(N)]
def LCS(x, y, m, n):
    # Since the length of subsequence at (0,0) is 0, L has (m+1, n+1) indices to store values of the lengths of the subsequences
    # go through each row
    for i in range(m+1):
        # go through each column
        for j in range(n+1):
            # if they are the first indices, mark it as 0 in L
            if i==0 or j==0:
                L[i][j] = 0
            # if characters of x and y match in (i-1, j-1), respective lengths at (i,j) of L will be updated
            elif x[i-1] == y[j-1]:
                L[i][j] = 1 + L[i-1][j-1]
            # if characters of x and y don't match, (i,j) of L is filled by the maximum of the lengths of the adjacent cells of (i,j)
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
    return L[m][n]

def findLCS(x, y, m, n):
    # set to store all possible LCS
    s = set()
    # if we reached the top matrix
    if m==0 or n==0:
        s.add("")
        return s
    # if last characters match, get the set from the matrix bounded by x[0..m-2] and y[0...n-2]
    if x[m-1] == y[n-1]:
        temp = findLCS(x, y, m-1, n-1)
        # for each of the LCS inside temp set, append the current character, because it matched.
        for string in temp:
            s.add(string+x[m-1])
    # if last characters don't match, then either go with top matrix or left matrix
    else:
        # if LCS can be constructed from the top of the matrix. Keep s as the set for top side of the matrix. We will merge the sets
        # of top and left side of the matrices whenever L[m-1][n] == L[m][n-1]
        if L[m-1][n]>=L[m][n-1]:
            s = findLCS(x, y, m-1, n)
        # if LCS can be constructed from the left side of the matrix
        if L[m][n-1]>=L[m-1][n]:
            temp = findLCS(x, y, m, n-1)
            # if L[m-1][n] == L[m][n-1], then we need to merge both sets. 
            for i in temp:
                s.add(i)
    return s
# Driver Code
if __name__ == "__main__":
    x = "AGTGATG"
    y = "GTTAG"
    m = len(x)
    n = len(y)
 
    print("LCS length is", LCS(x, y, m, n))
 
    s = findLCS(x, y, m, n)
     
    for i in s:
        print(i)
# -

# ## 7. Shortest Superstring Problem
#
# Given a set of n strings arr[], find the smallest string that contains each string in the given set as substring. We may assume that no string in arr[] is substring of another string.
#

# +
# string to store the resultant string of the maximum overlapping pair of strings
string = ""
def findShortestSuperString(arr, len):
    global string
    # run len-1 times to consider every pair
    while len!=1:
        # max stores the maximum overlap
        max = float("-inf")
        # l and r stores the array indices of the maximum overlapping strings
        l = 0
        r = 0
        # store the final resultant string after maximum overlap
        resultStr = ""
        # Go through all indices of array
        for i in range(len):
            # go through each pair of i
            for j in range(i, len):
                # get the maximum length of the overlap. This function even updates global string to store the resultant string after overlap
                res_len = findOverlappingPair(arr[i], arr[j])
                # Update max, resultStr, l and r
                if res_len>max:
                    max = res_len
                    resultStr = string
                    l = i
                    r = j
        # We store the string at the last index in r, if there is overlap
        # or if there is no overlap, we simply add the string at last index to the string at first index
        # hence we can safely reduce the length of the arr to not include the last string again 
        len -= 1
        # if there is no overlap, we add last string to the first string
        if max == float("-inf"):
            # note that the length is reduced in the previous code line. So, the index for the last index of the string 
            # is updated length.
            arr[0] += arr[len]
        # if there is overlap, we store the resultStr at l 
        # and last string at index r (why? because strinng previously at r is appended to string at l)
        else:
            arr[l] = resultStr
            arr[r] = arr[len]
    # string stored at first index is the super string
    return arr[0]

def findOverlappingPair(str1, str2):
    global string
    # max stores the maximum overlap
    max = float("-inf")
    # len1 and len2 stores the lengths of str1 and str2
    len1 = len(str1)
    len2 = len(str2)
    # store the minimum of len1 and len2
    min_len = min(len1, len2)
    # check if suffix of str1 matches with prefix of str2
    for i in range(1, min_len):
        # compare last i characters in str1 with first i characters in str2
        if str1[len1-i:] == str2[:i]:
            # if i is greater than max
            if i>max:
                # update max
                max = i
                # string stores the str1 appended with the rest of the string in str2 after i
                string = str1 + str2[i:]
    # check if suffix of str2 matches with prefix of str1
    for i in range(1, min_len):
        # compare last i characters in str2 with first i characters in str1
        if str2[len2-i:] == str1[:i]:
            # if i is greater than max
            if i>max:
                max = i
                # string stores the str2 appended with the rest of the string in str1 after i
                string = str2+str1[i:]
    return max
arr = ["catgc", "ctaagt", "gcta", "ttca", "atgcatc"]
arr_len = len(arr)
print(f"The Shortest Superstring is {findShortestSuperString(arr, arr_len)}")


# -

# ## 8. Longest Common Subsequence | DP-4
#
# LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. 
#
# It is a classic computer science problem, the basis of diff (a file comparison program that outputs the differences between two files), and has applications in bioinformatics.

# +
def lcs(X, Y, m, n):
    # Base case: in bottom-up approach, we have checked all the characters of X and Y. Lengths have become 0
    if m==0 or n==0:
        return 0
    # last characters of X and Y match. Hence, increase the length of the previous matrix by 1. By matrix, I mean X[0..m-1] and Y[0..n-1]
    elif X[m-1]== Y[n-1]:
        return 1+lcs(X, Y, m-1, n-1)
    # last characters don't match. Hence, length will be maximum of the lengths of 
    # either top (X[0..m-1], Y[0..n]) or left matrix (X[0..m], Y[0..n-1])
    else:
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))

# Driver program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print ("Length of LCS is ", lcs(X , Y, len(X), len(Y)))
# -

# ## 9. Find the first non-repeating character from a stream of characters
#
# Given a stream of characters, find the first non-repeating character from stream. You need to tell the first non-repeating character in $O(1)$ time at any moment.

# +
MAX_CHAR = 256
def findFirstNonRepeating(stream):
    inDLL = []* MAX_CHAR
    repeated = [False]*MAX_CHAR
    for i in range(len(stream)):
        x = stream[i]
        print(f"Reading {x} from stream")
        if not repeated[ord(x)]:
            if x not in inDLL:
                inDLL.append(x)
            else:
                inDLL.remove(x)
                repeated[ord(x)] = True
        if len(inDLL)!=0:
            print(f"First non-repeating character so far is {str(inDLL[0])} \n")

stream = "geekforgeekandgeeksandquizfor"
findFirstNonRepeating(stream)
 
# -

# ## 10. Check whether two strings are anagram of each other
#
# Write a function to check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains the same characters, only the order of characters can be different. For example, “abcd” and “dabc” are an anagram of each other.

# +
MAX_CHAR = 256
def areAnagram(str1, str2):
    # count to store the difference of counts of characters of str1 and str2
    count = [0 for i in range(MAX_CHAR)]
    # if lengths differ, then they are not anagrams
    if len(str1) != len(str2):
        return False
    # fill the count array
    for i in range(len(str1)):
        count[ord(str1[i]) - ord('a')]+=1
        count[ord(str2[i]) - ord('a')]-=1
    # if any count value is non-zero, then it is not anagram
    for i in range(MAX_CHAR):
        if count[i] != 0:
            return False
    return True

str1="geeksforgeeks"
str2="forgeeksgeeks"
 
# Function call
if (areAnagram(str1, str2)):
    print("The two strings are anagram of each other")
else:
    print("The two strings are not anagram of each other")


# -

# ## 11. Lexicographically n-th permutation of a string
#
# Given a string of length m containing lowercase alphabets only. You have to find the n-th permutation of string lexicographically.

# +
def next_permutation(list_char):
    # n stores the length of the list of characters sorted in the string
    n = len(list_char)
    # start from second to last index
    i = n-2
    # for next permutation
    # while this index doesn't become negative and next character at i+1 is lesser than the character at i, move back, since
    # we have used all next permutations until that point
    while i>=0 and list_char[i]>=list_char[i+1]:
        i -= 1
    # if index becomes negative, we have explored all next permutations
    if i==-1:
        return False
    # j stores the index of the subarray after ith index. Ultimately, it will store the character's index which will be swapped with character
    # at i, (for the next permutation)
    j = i+1
    # while j doesn't become n (length of the list_char) and character at j is greater than character at i, move j to next index
    while j<n and list_char[j]>list_char[i]:
        j += 1
    # j becomes next index, before while loops end. So, reduce j by 1
    j -= 1
    # swap characters at j and i
    list_char[j], list_char[i] = list_char[i], list_char[j]
    # For getting
    # left stores the index of character, next to ith character. 
    left = i+1
    # right pointer stores the index of last character
    right = n-1
    # move left and right points such that their characters are swapped, and then we reduce the size of the sub-array bounded by left and right
    # pointers by moving left point to next and right point to its previous index
    while left<right:
        list_char[left], list_char[right] = list_char[right], list_char[left]
        left += 1
        right -= 1
    return True

def n_permute(string, nth):
    # string list makes the list of the input string
    string = list(string)
    # new_string will store the result of the nth permutation
    new_string = []
    # sort the string list to be fed as input to next_permutation()
    string.sort()
    # index_perm stores the #permutations that occured till now.
    count_perm = 1  # let's say you want 2nd permutation, when count_perm becomes two, you will break the following loop

    while next_permutation(string):
        new_string = string
        count_perm += 1
        if count_perm==nth:
            break
        
    print(''.join(new_string))

if __name__ == "__main__":
    string = "ABC"
    nth = 2
    nPermute(string, nth)


# -

# ## 12. How to find Lexicographically previous permutation?
#
# Given a word, find lexicographically smaller permutation of it. For example, lexicographically smaller permutation of “4321” is “4312” and next smaller permutation of “4312” is “4231”. If the string is sorted in ascending order, the next lexicographically smaller permutation doesn’t exist.
#
#
#

# +
def prevPermutation(str):
 
    # Find index of the last element
    # of the string
    n = len(str) - 1
 
    # Find largest index i such that
    # str[i - 1] > str[i]
    i = n
    while (i >= 0 and str[i - 1] <= str[i]):
        i -= 1
 
    # if string is sorted in ascending order
    # we're at the last permutation
    if (i <= 0):
        return False, "No previous permutation"
 
    # Note - str[i..n] is sorted in
    # ascending order
 
    # Find rightmost element's index
    # that is less than str[i - 1]
    j = i - 1
    while (j + 1 <= n and
           str[j + 1] <= str[i - 1]):
        j += 1
 
    # Swap character at i-1 with j
    str = list(str)
    temp = str[i - 1]
    str[i - 1] = str[j]
    str[j] = temp
    str = ''.join(str)

    # Reverse the substring [i..n]
    # str[::-1]
 
    return True, str
 
 
# Driver code
if __name__ == '__main__':
    str = "ABCD"
 
    b, str = prevPermutation(str)
 
    if (b == True):
        print("Previous permutation is", str)
    else:
        print("Previous permutation doesn't exist")
# -

# ## 13. Find n-th lexicographically permutation of a string | Set 2
#
# Given a string of length m containing lowercase alphabets only. We need to find the n-th permutation of string lexicographically.

# +
MAX_CHAR = 26
MAX_FACT = 20
fact = [None] * (MAX_FACT)
 
# Utility for calculating factorials
def precomputeFactorials():
 
    fact[0] = 1
    for i in range(1, MAX_FACT):
        fact[i] = fact[i - 1] * i
 
# Function for nth permutation
def nPermute(string, n):
 
    precomputeFactorials()
 
    # length of given string
    length = len(string)
 
    # Count frequencies of all
    # characters
    freq = [0] * (MAX_CHAR)
    for i in range(0, length):
        freq[ord(string[i]) - ord('a')] += 1
 
    # out string for output string
    out = [None] * (MAX_CHAR)
 
    # iterate till sum equals n
    Sum, k = 0, 0
 
    # We update both n and sum in
    # this loop.
    while Sum != n:
 
        Sum = 0
         
        # check for characters present in freq[]
        for i in range(0, MAX_CHAR):
            if freq[i] == 0:
                continue
 
            # Remove character
            freq[i] -= 1
 
            # calculate sum after fixing
            # a particuar char
            xsum = fact[length - 1 - k]
            for j in range(0, MAX_CHAR):
                xsum = xsum // fact[freq[j]]
            Sum += xsum
 
            # if sum > n fix that char as
            # present char and update sum
            # and required nth after fixing
            # char at that position
            if Sum >= n:
                out[k] = chr(i + ord('a'))
                n -= Sum - xsum
                k += 1
                break
             
            # if sum < n, add character back
            if Sum < n:
                freq[i] += 1
         
    # if sum == n means this char will provide
    # its greatest permutation as nth permutation
    i = MAX_CHAR-1
    while k < length and i >= 0:
        if freq[i]:
            out[k] = chr(i + ord('a'))
            freq[i] -= 1
            i += 1
            k += 1
         
        i -= 1
 
    # print result
    print(''.join(out[:k]))
 
# Driver Code
if __name__ == "__main__":
 
    n = 2
    string = "abc"
 
    nPermute(string, n)

# -

# ## 14. Next Permutation
#
# Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
#
# >"**Algorithm: Single Pass Approach**"
#
# $ O(N), O(N) $

# +
def nextPermutation(num):
    # index such that digit at this index is lesser than the digit at its next index
    i = len(num) - 2
    # keep reducing i while i is non-negative and digit at i is greater than or equal to digit at i+1
    while i>=0 and num[i]>=num[i+1]:
        i -= 1
    if i>=0:
        # index such that the digit at this index will be the first digit to be greater than the digit at i
        j = len(num)-1
        # keep reducing j such that digit at j is lesser than or equal to digit at i
        while num[j]<=num[i]:
            j -= 1
        swap the digits at i and j
        num[i], num[j] = num[j], num[i]
    # reverse the digits i+1 onwards to get the next permutation
    reverse(num, i+1)
    return num
def reverse(num, start):
    i = start
    j = len(num)-1
    while i<j:
        num[i], num[j] = num[j], num[i]
        i += 1
        j -= 1

num = [1,2, 3]
nextPermutation(num)


# -

# ## 15. Minimum Swaps for Bracket Balancing
#
# You are given a string of 2N characters consisting of N ‘[‘ brackets and N ‘]’ brackets. A string is considered balanced if it can be represented in the for S2[S1] where S1 and S2 are balanced strings. We can make an unbalanced string balanced by swapping adjacent characters. Calculate the minimum number of swaps necessary to make a string balanced.

def swapCount(string):
    # count the number of left and right brackets
    countLeft, countRight = 0, 0
    # list of characters in input string
    chars = list(string)
    # swap stores the number of swaps requiured. imbalance stores the number of imbalanced pairs
    swap, imbalance = 0, 0
    # go through each character
    for i in range(len(chars)):
        # if it is [, increment countLeft
        if chars[i] == '[':
            countLeft += 1
            # imbalance is greater than 0, increment swap by imbalance
            if imbalance>0:
                swap += imbalance
                # since one imbalance pair is solved, reduce that by 1
                imbalance -= 1
        # if it is ]
        elif chars[i] == ']':
            # increment right brackets count by 1
            countRight += 1
            # imbalance is difference of number of right and left brackets
            imbalance = countRight - countLeft
    return swap
s = "[]][]["
swapCount(s)


# ## 16. Length of Longest Balanced Subsequence
#
# > "Given a string S, find the length of the longest balanced subsequence in it. A balanced string is defined as:- "
#
# 1. A null string is a balanced string.
# 2. If X and Y are balanced strings, then (X)Y and XY are balanced strings.

def maxLength(string, n):
    # invalidOpen to store the #open brackets that do not have corresponding closing bracket
    invalidOpen , invalidClose = 0, 0
    # list of characters in the string
    chars = list(string)
    # iterate through string via index i
    for i in range(len(chars)):
        # if character is (
        if chars[i] == '(':
            # increment invalidOpenBrackets by 1 (that haven't been closed)
            invalidOpen += 1
        # the character is )
        else:
            # if there are no open brackets, increment invalidClose by 1
            if invalidOpen == 0:
                invalidClose += 1
            # found matching open brackets, so decrement imbalance pair by 1
            else:
                invalidOpen -= 1
    return n-invalidOpen-invalidClose
s = "()(((((()"
n = len(s)
maxLength(s, n)


# ## 17. Find maximum depth of nested parenthesis in a string
#
# We are given a string having parenthesis like below 
#
# `“( ((X)) (((Y))) )”`
#
# We need to find the maximum depth of balanced parenthesis, like 4 in the above example. Since ‘Y’ is surrounded by 4 balanced parentheses. 
# If parenthesis is unbalanced then return -1. 

def maxDepth(string):
    # list of charcters in string
    chars = list(string)
    # current_max stores the number of opening brackets until we find closing brackets. That's when we reduce it by 1 per 1 closing bracket
    # max stores the maximum depth
    current_max, max = 0, 0
    n = len(chars)
    # go through all characters
    for i in range(n):
        # if it is an opening bracket
        if chars[i] == '(':
            # increase current_max by 1
            current_max += 1
            # update max if required
            if current_max > max:
                max = current_max
        # if it is a closing bracket
        elif chars[i] == ')':
            # current_max has opening brackets, reduce them since we found a matching closing bracket
            if current_max>0:
                current_max -= 1
            # no opening bracket, we find unbalanced paranthesis
            else:
                return -1
    # if imbalanced paranthesis
    if current_max!=0:
        return -1
    return max
s = "( ((X)) (((Y))) )"
maxDepth(s)


# ## 18. Find the smallest window in a string containing all characters of another string
#
# Given two strings, string1 and string2, the task is to find the smallest substring in string1 containing all characters of string2 efficiently.

def minWindow(s, t):
    ans = 10**9
    start = 0
    count = 0
    m = [0 for i in range(256)]
    for i in range(len(t)):
        if m[ord(t[i])-ord('a')]==0:
            count += 1
        m[ord(t[i])-ord('a')] += 1
    i, j = 0, 0
    while j<len(s):
        m[ord(s[j])-ord('a')] -= 1
        # m stores the occurences of characters in t. If any character in m has value 0 with it, it means that we have processed t's character
        if m[ord(s[j])-ord('a')]==0:
            count -= 1
        # if count has reached 0, we have got the window
        if count==0:
            while count==0:
                if j-i+1<ans:
                    ans = min(ans, j-i+1)
                    start = i
                m[ord(s[i])-ord('a')] += 1
                # increase count if the value of character in m is greater than 0 (situation with t's characters) ie if t's character's value is increased
                if m[ord(s[i])-ord('a')]>0:
                    count += 1    
                i += 1
        j += 1
    
    if ans != 10**9:
        return s[start:start+ans]
    else:
        return -1
s = "ADOBECODEBANC"
t = "ABC"
print("-->Smallest window that contain all character : ")
print(minWindow(s, t))

StarcoderdataJupyterScriptsDedupFiltered