Snapshot Array - Python Solution

 Implement a SnapshotArray that supports the following interface:

• SnapshotArray(int length) initializes an array-like data structure with the given length.  Initially, each element equals 0.
• void set(index, val) sets the element at the given index to be equal to val.
• int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
• int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

 

Example 1:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

class SnapshotArray:

    def __init__(self, length: int):
        self.A = [{} for _ in range(length)]
        self.snap_id = 0

    def set(self, index: int, val: int) -> None:
        self.A[index][self.snap_id] = val

    def snap(self) -> int:
        self.snap_id +=1
        return self.snap_id-1

    def get(self, index: int, snap_id: int) -> int:
        snaps = self.A[index]
        if snap_id in snaps:
            return snaps[snap_id]
        else:
            last_val = 0
            for i in range(0,self.snap_id+1):
                if i in snaps:
                    last_val = snaps[i]
                if i >= snap_id:
                    return last_val
            return last_val


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)

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)