Coding Problem 7

-

                  Longest Substring 

                                                  asked by Amazon


Ques. Given an integer K and string S, find the length of the longest substring that contains at most K distinct characters. For example, given S = "abcba" and  K = 2 , the longest substring with K distinct characters is "bcb".


Solution.

This problem can be solved by many methods but time complexity will be high. There is a solution of O(n) time complexity. We can use the method of sliding window here. In the window it will contain the substring and it will be stable if it contains K distinct characters at any point. If window contains less than K charcaters then we expand the windw by adding more characters from the right side otherwise if window contains more than K distinct charcaters we will shrink the window by deleting the characters from left side of window. We will continue the same process untill we reach the last characters from the string. At the time of window moving we can take care of longest substring size also.We gonna need the list or set to keep the frequencies of characters in the string becuase a charcater can occur many times. So if we add the character into window we add the count of frequency and if we remove it from the window then we will descrease the count. To keep the frequency we are gonna need the long array or set which will keep the track of count at the index equal to ASCII value of charcater. It will make easy for us to access the frequency of character. ord() function will be used to access the ASCII value of charcater. Lets see the code now - 


def longestSubstr(s, k):

    end = begin = 0     # boundaries of substring 

    window = set()     # store characters

    freq = [0]*256       # store the frequency of char currently in the window

    low = high = 0        # sliding window boundaries 

    while high < len(s):

        window.add(s[high])

        freq[ord(s[high])] += 1

        

        while len(window) > k:

            freq[ord(s[low])] -= 1

            if freq[ord(s[low])] == 0:

                window.remove(s[low])

            low += 1

        

        # check if substring size is increased then update the value

        if end-begin < high-low:  

            end = high

            begin = low

        high += 1

    return s[begin:end + 1]


s = 'abbcddba'

k = 2

print(longestSubstr(s, k))


Output : "abb"


Note : There can be multiple answers for a string just like above case, we have print out any one of them.

Comments

Post a Comment

Popular posts from this blog

Coding Problem 10

-
Image
                                Minimum Cost Required                                                        asked by Facebook Ques. A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost while ensuring that no two neighbouring houses are of same color. Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth color return the minimum cost which achieves this goal. Solution.   Suppose we have cost matrix like this - [ [2, 1, 1],   [1, 10, 3],   [1, 2, 100]  ] Each row represents the house and each column represents the color so the values are the cost of painting the color for a house. Since we know that indexes starts from 0 so cost of pain...
Read more

Coding Problem 3

-
             Sum of Numbers in List                                                      asked by Google Ques. Given a list of numbers and a integer K return whether any two numbers from the list will add upto K or not. For example - Given list is [10, 15, 3, 7] and K = 17, then return True because 10 + 7 = 17. Solution.   So basically we have to find the two numbers that are present in the list and sum of both is equal to K. So we can simply run two loops on the list and check each pair of number if they are equal to K or not. This method is Brute-force and complexity is O(n^2). What we can do here is run the loop over the list and then subtract that number from the target and check whether the remaining number is present in the list or not. Lets see the code  def find_numbers(inp_list, K):    ...
Read more

Coding Problem 9

-
                                    Maximum in Subarray                                                          asked by Google Ques. Given an array of integers and a number k, where 1<= k <= length of array, compute the maximum values of each subarray of length k. For example - given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get [10, 7, 8, 8], since  10 = max(10, 5, 2) 7 = max(5, 2, 7) 8 = max(2, 7, 8) 8 = max(7, 8, 7) Solution. This question has a simple solution. In array we will create a window which consist of number of elements equal to k and can find the maximum among them and append that in output list. But while traversing the array we have to keep something very important in mind. We will not traverse from index 0 to nth index...
Read more