Android Unlock Patterns - Python Solution

 Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

 

Rules for a valid pattern:

1. Each pattern must connect at least m keys and at most n keys.
2. All the keys must be distinct.
3. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
4. The order of keys used matters.

 

 

Explanation:

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |

Invalid move: 4 - 1 - 3 - 6
Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2
Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6
Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2
Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

 

Example:

Input: m = 1, n = 1
Output: 9

class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        skip = {}
        skip[(1,3)] = 2
        skip[(1,7)] = 4
        skip[(1,9)] = 5
        skip[(2,8)] = 5
        skip[(3,7)] = 5
        skip[(3,9)] = 6
        skip[(4,6)] = 5
        skip[(7,9)] = 8
        self.ans = 0
        def dfs(visited,k):
            if len(visited) >= m:
                self.ans+=1
            if len(visited) == n:
                return 
            for i in range(1,10):
                if i not in visited:
                    pair = (min(k,i),max(k,i))
                    if pair not in skip or skip[pair] in visited:
                        dfs(visited + [i],i)
        dfs([1],1)
        dfs([2],2)
        self.ans *=4
        dfs([5],5)
        return self.ans

O(n) TC SC O(1)

Find And Replace in String - Python Solution

 To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y.  The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y.  If not, we do nothing.

For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".

Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = 'c', which doesn't match x[0] = 'e'.

All these operations occur simultaneously.  It's guaranteed that there won't be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

Example 1:

Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation: "a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".

Example 2:

Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it's replaced by "eee". 
"ec" doesn't starts at index 2 in the original S, so we do nothing.

Notes:

1. 0 <= indexes.length = sources.length = targets.length <= 100
2. 0 < indexes[i] < S.length <= 1000
3. All characters in given inputs are lowercase letters.

class Solution:

    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:

        hashmap ={i:(src,tar) for i,src,tar in zip(indexes,sources,targets)}

        result = ""

        i = 0

        while i < len(S):

            if i in hashmap and S[i:].startswith(hashmap[i][0]):

                result +=hashmap[i][1]

                i+=len(hashmap[i][0])

            else:

                result += S[i]

                i+=1

        return result

      

O(N) - > TC and SC

Minimum Window Substring - Python Solution

 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        dict_t = Counter(t)
        required = len(dict_t)
        filtered_s = []
        for i,char in enumerate(s):
            if char in dict_t:
                filtered_s.append((i,char))
        l,r = 0,0
        formed = 0
        window_counts = {}
        ans = float("inf"),None,None
        while r < len(filtered_s):
            character = filtered_s[r][1]
            window_counts[character] = window_counts.get(character,0)+1
            if window_counts[character] == dict_t[character]:
                formed+=1
                
            while l<=r and formed == required:
                character = filtered_s[l][1]
                
                end = filtered_s[r][0]
                start = filtered_s[l][0]
                if end-start+1 < ans[0]:
                    ans = (end-start+1,start,end)
                
                window_counts[character] -=1
                if window_counts[character] < dict_t[character]:
                    formed-=1
                l +=1
            r+=1
        return "" if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

TC: O(∣S∣+∣T∣) SC:O(∣S∣+∣T∣)

Longest Substring Without Repeating Characters - Python Solution

 Given a string s, find the length of the longest substring without repeating characters.

 

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        left,right = 0,0
        max_len = 0
        hashmap = collections.defaultdict()
        while right < n:
            if s[right] in hashmap:
                left = max(hashmap.get(s[right]),left)
            max_len = max(max_len,right-left+1)
            hashmap[s[right]] = right+1
            right = right+1
        return max_len  

TC: O(n) SC: O(n)

Longest Substring with At Most K Distinct Characters - Python Solution

 Given a string, find the length of the longest substring T that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        if n <= k:
            return n
        left,right = 0,0
        max_len = k
        hashmap = collections.defaultdict()
        while right < n:
            # inserting the last index of the distinct elements
            if len(hashmap) <= k:
                hashmap[s[right]] = right
                right+=1
            
            # when we have more than k distinct elements
            #we need to move the left pointer 
            if len(hashmap) == k+1:
                del_idx = min(hashmap.values())
                del hashmap[s[del_idx]]
                left = del_idx+1
            max_len = max(max_len,right-left)
        return max_len   

TC: O(n) SC: O(n)

Longest Substring with At Most Two Distinct Characters - Python Solution

 Given a string s , find the length of the longest substring t  that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        k = 3
        n = len(s)
        if n < k:
            return n
        left,right = 0,0
        max_len = 2
        hashmap = collections.defaultdict()
        while right < n:
            # inserting the last index of the distinct elements
            if len(hashmap) < k:
                hashmap[s[right]] = right
                right+=1
            
            # when we have more than k-1 or 2 distinct elements
            #we need to move the left pointer 
            if len(hashmap) == k:
                del_idx = min(hashmap.values())
                del hashmap[s[del_idx]]
                left = del_idx+1
            max_len = max(max_len,right-left)
        return max_len   
                

TC: O(n) SC: O(n)

Shortest Path in a Grid with Obstacles Elimination - Python Solution

 Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

 

Example 1:

Input: 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
Output: 6
Explanation: 
The shortest path without eliminating any obstacle is 10. 
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

 

Example 2:

Input: 
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
Output: -1
Explanation: 
We need to eliminate at least two obstacles to find such a walk.

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int: 
        if len(grid) == 1 and len(grid[0]) == 1:
            return 0

        queue = deque([(0,0,k,0)]) // 
        visited = set([(0,0,k)])

        if k > (len(grid)-1 + len(grid[0])-1):
            return len(grid)-1 + len(grid[0])-1

        while queue:
            row, col, eliminate, steps = queue.popleft()
            for new_row, new_col in [(row-1,col), (row,col+1), (row+1, col), (row, col-1)]:
                if (new_row >= 0 and
                    new_row < len(grid) and
                    new_col >= 0 and
                    new_col < len(grid[0])):
                    if grid[new_row][new_col] == 1 and eliminate > 0 and (new_row, new_col, eliminate-1) not in visited:
                        visited.add((new_row, new_col, eliminate-1))
                        queue.append((new_row, new_col, eliminate-1, steps+1))
                    if grid[new_row][new_col] == 0 and (new_row, new_col, eliminate) not in visited:
                        if new_row == len(grid)-1 and new_col == len(grid[0])-1:
                            return steps+1
                        visited.add((new_row, new_col, eliminate))
                        queue.append((new_row, new_col, eliminate, steps+1))

        return -1