Cover image
Brian T. Liao
Aug 28, 2019 • 40 min read

Interview Cram II

They say teaching is the best way to learn.

Number of Islands

LeetCode

Problem

Given a 2d map, ‘1’ is an island space, and ‘0’ is an ocean space. An island is all island spaces connected. Count the number of islands.

Walkthrough

To get a whole island, we can use DFS to recursively see if spaces adjacent are also part of the same island. Once seen, mark it as ‘s’ so we won’t explore the space again.

We can use two for loops, going through each column and each row. On each new seen island, increase our counter, and DFS the island, updating each space to seen to not be double counted.

Techniques

Recursion, Search, Union-Find

Complexity

Time: O(m * n) where m is number of rows and n is number of columns. We have two for loops and run DFS on each space which is O(m * n) as well in the worst case.

DFS is O(|E|+|V|)?

Space: O(1) because we use the grid and never change the size.  

Python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # 5 variable for counting islands
        count = 0
        # 6 go through grid, seen islands are ignore as they are marked 's'
        for col in range(len(grid)):
            for row in range(len(grid[col])):
                if grid[col][row] == '1':
                    count += 1
                    self.dfs(grid, row, col)
        return count
                
        
    def dfs(self, grid, row, col) -> int:
        # 1 check if block's out of bounds
        if col < 0 or col >= len(grid):
            return
        if row < 0 or row >= len(grid[0]):
            return
        # block is in bounds
        # 2 check if block is island
        if grid[col][row] == '1':
            # 3 block is seen
            grid[col][row] = 's'
            # 4 dfs your blocks's north, south, east, west (connected blocks)
            self.dfs(grid, row + 1, col)
            self.dfs(grid, row - 1, col)
            self.dfs(grid, row, col + 1)
            self.dfs(grid, row, col - 1)

Java

class Solution {
    public int numIslands(char[][] grid) {
        // 5. variable to count number of islands
        int count = 0;
        // 6. go through the grid, run dfs on new islands seen. seen islands are marked 's'
        for (int col = 0; col < grid.length; col++) {
            for (int row = 0; row < grid[0].length; row++) {
                if (grid[col][row] == '1') {
                    count += 1;
                    dfs(grid, row, col);
                }
            }
        }
        return count;
    }
    
    public void dfs(char[][] grid, int row, int col) {
        // 1. check spot is in bounds
        if (col < 0 || col >= grid.length) {
            return;
        }
        if (row < 0 || row >= grid[0].length) {
            return;
        }
        // 2. check spot is island
        if (grid[col][row] != '1') {
            return;
        }
        
        // 3. set spot to seen
        grid[col][row] = 's';
        
        // 4. recursive check left, right, up, and down of spot.
        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row, col + 1);
    }
}

Coin Change

LeetCode

Problem

Given a list of different coin values and a goal value, give the minimum number of coins to make the goal value, or -1 if not possible.

Walkthrough

We can use dynamic programming, our subproblems is for a value i, arr[i], the min number of coins is min(arr[i], 1 + arr[i - coin]) for all coins. Initialize each value to ‘inf’ and loop from 0 to i and return arr[value] or -1 if not possible (arr[value] will still be ‘inf’).

subproblem? want for value i, want min number of coins. arr[i] = min(arr[i], 1 + arr[i - coin]) for all coins
java has an overflow issue

Techniques

Dynamic Programming and Recursion

Complexity

Time: O(m * n) where m is number of coins and n is the goal value. We have two for loops, the inner loop on coins solves subproblems, and the outer loop iterates the subproblems we solve.

Space: O(n) need a cache for goal.  

Python

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 1. create an array for the min amount of coins that make each index amount
        # 2. set each value to infinity in case it is not possible to make that amount of coins
        # 3. set index 0 to 0 because it takes 0 of each coins to make $0. Base Case.
        minNumCoinsToMakeAmount = [float('inf')] * (amount + 1)
        minNumCoinsToMakeAmount[0] = 0
        # 4. solve each subproblem in order (including amount)
        for curAmount in range(amount + 1):
            # 5. solve the subproblem. Min number of coins using each coin.
            for coin in coins:
                # 6. check the coin value is less than the curAmount. If not, we will get a negative index, out of bounds.
                if coin <= curAmount:
                    # update if using this coin (1 + num coins to make this amount with the coin value subtracted) is less than currently. This removes 'inf' if it is possible to make the coin amount
                    minNumCoinsToMakeAmount[curAmount] = min(minNumCoinsToMakeAmount[curAmount], 1 + minNumCoinsToMakeAmount[curAmount - coin])
        # if the array has a value for amount, it is possible. Else if it's 'inf', it's not possible and return -1.
        return minNumCoinsToMakeAmount[amount] if minNumCoinsToMakeAmount[amount] != float('inf') else -1

Java

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 1. array for dynamic programming to the coin amount
        int[] fewestCoinsToAmount = new int[amount + 1];        
        // 2. get the value of number of coins to each ammount
        for (int currentAmount = 1; currentAmount <= amount; currentAmount++) {
            // 3. Use Integer.MAX_VALUE as a placeholder in case no coin combination
            fewestCoinsToAmount[currentAmount] = Integer.MAX_VALUE;
            // 4. count number of way using each type of coin
            for (int coin : coins) {
                // 5. currentAmount must be greated than the coin value and previous coin value has a number of ways
                if (currentAmount >= coin && fewestCoinsToAmount[currentAmount - coin] != Integer.MAX_VALUE) {
                    // 6. update if the number of coins with this coin is less than current number of coins
                    int numCoinsWithCurrentCoin = 1 + fewestCoinsToAmount[currentAmount - coin];
                    if (numCoinsWithCurrentCoin < fewestCoinsToAmount[currentAmount]) {
                        fewestCoinsToAmount[currentAmount] = numCoinsWithCurrentCoin;
                    }
                }
            }
        }
        int numberOfCoins = fewestCoinsToAmount[amount];
        // 7. check that there is a way to make the amount with the coins given
        if (numberOfCoins == Integer.MAX_VALUE) {
            return -1;
        }
        return numberOfCoins;
        
    }
}

Notes

Why is the dynamic programming array size amount + 1? What is the dynamic programming array called. “Cache?”

How to solve Dynamic Programming?

  1. decide parameters to index on and what they represent
  2. find base cases
  3. find recurrence relation
  4. find a valid iteration order and what to return

Edit Distance

LeetCode

Problem

Given word1 and word2, find the minimum number of operations required to convert word1 to word2. Operations are inserting a character, deleting a character, and replacing a character.

Walkthrough

We can build up a solutiøn by solving subproblems. The cost of moving from a subword1 to a subword2 is first check if the final character is the same. Consider raptor. A subword that are the same are rapt and rapt. Both are the same so there is no operation done from rap and rap. Consider rapt and rapp. Here we need to replace a character. Which is just replace t with p from the subproblem of rap to rap. The alternative is removing a character or adding a character to either word. By creating a editDistance dynamic programming cache, we can solve the subproblems so solve the final solution.

Techniques

Dynamic Programming and Recursion

Complexity

Let m be the length of word1 and n be the distance of word2.

Time Complexity: O(m * n) from going through each subproblem of each word1 subword to each word2 subword.

Space Complexity: O(m * n) from the editDistance dynamic programming cache for each subproblem.

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # 1. Have a 2d array where col, row is number of operations to go from word 1 to word 2
        # why + 1? Consider 'horse' len -> 5 index 0 to 4. Want "" as 0 so e is 5
        edit_distance = [[float('inf') for row in range(len(word1) + 1)] for col in range(len(word2) + 1)]
        # 2. empty string to empty string is 0. So col 0 row 0 is 0. 'h' to '' is 1, so col 1, row 0 is 1. 
        # 'ho' to '' is 2, so col 2, row 0 is 2 and so on. This is our base case.
        for col in range(len(edit_distance)):
            edit_distance[col][0] = col
        # 3. do the same for string 1 to string 2. I reversed col and row for word1 and 2.
        for row in range(len(edit_distance[0])):
            edit_distance[0][row] = row
        # 4. Solve each subproblem for row 1. Then row 2 and so on.
        for col in range(1, len(edit_distance)):
            for row in range(len(edit_distance[0])):
                # 5. subproblem: If letters at the index are equal, edit_distance (ed) is the changes
                # up to the previous character. ed[row][col] = ed[row - 1][col - 1]
                # else ed is the min of adding a character to col, to row, or changing a character
                # ed[col][row] = min([1 + ed[col - 1][row], 1 + ed[col][row - 1], 1 + ed[col - 1][row - 1]])
                if row > 0 and word2[col - 1] == word1[row - 1]:
                    edit_distance[col][row] = edit_distance[col - 1][row - 1]
                else:
                    edit_distance[col][row] = min([1 + edit_distance[col - 1][row],
                                                   1 + edit_distance[col][row - 1],
                                                   1 + edit_distance[col - 1][row - 1]])
        # 6. return edit distance from all characters of word 1 to word 2
        return edit_distance[len(word2)][len(word1)]

Java

class Solution {
    public int minDistance(String word1, String word2) {
        // 1. Have a cost cache of subproblems cost to go from word1 to word2. Add 1 to both for a space for ''
        int[][] editDistanceCost = new int[word1.length() + 1][word2.length() + 1];
        // 2. set up for both word1 to word2 as '' and word2 to word1 as ''
        for (int row = 0; row < word1.length() + 1; row++) {
            editDistanceCost[row][0] = row;
        }
        for (int col = 0; col < word2.length() + 1; col++) {
            editDistanceCost[0][col] = col;
        }
        // 3. solve each subproblem for each subword1 to subword2 in order
        for (int row = 1; row < word1.length() + 1; row++) {
            for (int col = 1; col < word2.length() + 1; col++) {
                // 4. If both subwords are equal, cost is how much cost without the latest added letter
                // else it's the min of the cost to add/remove one character from word1, or from word2, or replace a character
                if (word1.charAt(row - 1) == word2.charAt(col - 1)) {
                    editDistanceCost[row][col] = editDistanceCost[row - 1][col - 1];
                } else {
                    int replaceCost = 1 + editDistanceCost[row - 1][col - 1];
                    int addToWord1Cost = 1 + editDistanceCost[row - 1][col];
                    int addToWord2Cost = 1 + editDistanceCost[row][col - 1];
                    int minCost = replaceCost;
                    if (addToWord1Cost < minCost) {
                        minCost = addToWord1Cost;
                    } else if (addToWord2Cost < minCost) {
                        minCost = addToWord2Cost;
                    }
                    editDistanceCost[row][col] = minCost;
                }
            }
        }
        // 5. return the general case solution, number of edits from word1 to word2;
        return editDistanceCost[word1.length()][word2.length()];
    }
}

Notes

Why do the subproblems work for adding and removing a letter?

Construct Binary Tree from Preorder and Inorder Traversal

LeetCode

Problem

Given a list as a preorder traversal of a tree and an inorder traversal of a tree, can you construct the original binary tree?

Techniques

Recursion Search Trees

Complexity

Time Complexity: O(n^2) Worst case everything is in a line. Each time we will have to find the index.

Possibly

Space Complexity: O(h) The height of the tree as our recrusive stack goes up h times. The array size never exceeds the limit.

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # 1. Preorder always has the top node of the tree first.
        # Inorder always has the nodes of left side of tree left of head node and nodes right side of the tree right of the head node.
        # Recursively split the tree and the preorder, inorder to solve the problem.
        # 2. Base case: empty inorder array
        if not inorder:
            return None
        # 3. get the head
        head = preorder.pop(0)
        # 4. split inorder into right of tree and left of tree
        index = inorder.index(head)
        left = inorder[:index]
        right = inorder[1+index:]
        # 5. Create the node to return. Set left and right to recursively building tree.
        node = TreeNode(head)
        node.left = self.buildTree(preorder, left)
        node.right = self.buildTree(preorder, right)
        return node

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder, int preorderIndex, int inorderStartIndex, int inorderEndIndex) {
        // 1. Base Case if inorder start and end index are the same (the recursive inorder list is empty)
        if (inorderStartIndex > inorderEndIndex) {
            return null;
        }
        // 2. In preorder the head of a tree is always the first element
        TreeNode head = new TreeNode(preorder[preorderIndex]);
        // 3. find head value in inorder array.
        int headValueIndexInorder = 0; // will be replaced
        for (int i = inorderStartIndex; i <= inorderEndIndex; i++) {
            if (inorder[i] == head.val) {
                headValueIndexInorder = i;
                break;
                
            }
        }
        // 4. Recursively call left and right trees. In inorder, all nodes left of head are left of headValueIndexInorder and all nodes right of head are right of headValueIndexInorder
        head.left = buildTree(preorder, inorder, preorderIndex + 1, inorderStartIndex, headValueIndexInorder - 1);
        head.right = buildTree(preorder, inorder, preorderIndex + headValueIndexInorder - inorderStartIndex + 1, headValueIndexInorder + 1, inorderEndIndex);
        return head;
        
    }
    
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // . call the Helper function with the index set to the sizes of the arrays
        return buildTree(preorder, inorder, 0, 0, inorder.length - 1);
    }
}

Notes

Java bounds checking was ‘>’. Java had to have index pointers and can’t just create new arrays. Can do postorder, just creat the tree right to left.

Find the Duplicate Number

LeetCode

Problem

Given an array with n + 1 integers between 1 to n inclusive, find the duplicate.

Techniques

Search

Complexity

Time: O(N) Never have to traverse the “linked list more than once”

Space: O(1) Only use the given array.

Python

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # 1. This problem can be seen as a linked list. At index 0, it points to index 1.
        # At index 1, it points to index 3. Therefore we are actually trying to find a cycle
        # in the linked list. We can solve this two pointers a fast rabbit pointer that jumps two
        # "nodes" and a slow turtle pointer that jumps one node. They will eventually land on
        # the same node. Refer to https://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work/32190575#32190575       
        
        rabbit_pointer = nums[0]
        turtle_pointer = nums[0]
        # 2. if we put the rabbit == turtle check here, it will break initially
        # Let x be the distance to the start of the cycle. Let Y be the distance to the meeting point.
        # Let Z be the remaining distance to the head of the cycle. The fast rabbit pointer 
        # traveled (x + y + z) one full cycle + y reaching the turtle. This is x + 2y + z.
        # The slow turtle pointer traveled x + y to the meeting point.
        while True:
            rabbit_pointer = nums[nums[rabbit_pointer]]
            turtle_pointer = nums[turtle_pointer]
            if rabbit_pointer == turtle_pointer:
                break
        # Since the rabbit is twice as fast as the turtle, it's distance is twice as much.
        # Therefore 2 * (x + y) = x + 2y + z => 2x + 2y = x + 2y + z => x = z.
        # Therefore to reach the head, have two pointers travel, one from the start and 
        # one from the meeting point to get to the head.
        head_pointer = nums[0]
        while head_pointer != turtle_pointer:
            head_pointer = nums[head_pointer]
            turtle_pointer = nums[turtle_pointer]
        return head_pointer

Java

class Solution {
    public int findDuplicate(int[] nums) {
        // 1. Since we have all number 1 to n inclusive, this can be seen as a linked list.
        // nums[0] points to index 1. nums[1] points to index 3, etc.
        // Therefore we can solve this as rabbit turtle cycle head detection.
        // A cycle meeting point will be found with a rabbit moving two steps and a
        // turtle moving one step as they will overlap.
        int rabbit = nums[0];
        int turtle = nums[0];
        while (true) {
            rabbit = nums[nums[rabbit]];
            turtle = nums[turtle];
            if (rabbit == turtle) {
                break;
            }
        }
        // 2. Let x be the distance to the head of the cycle, the duplicate number.
        // Let y be the distance to the meeting point of the rabbit and turtle.
        // Let z be the remainder of the cycle from end of y to the head of the cycle.
        // The rabbit moved a full cycle x + y + z and to the meeting point again + y for total of x + 2y + z.
        // The turtle moved to the meeting point x + y.
        // The rabbit is twice as fast so 2(x + y) = x + 2y + z => 2x + 2y = x + 2y + z => x = z.
        // Therefore to get the head and the duplicate number have a pointer at the start node,
        // and increment it and the turtle node till they match.
        int head = nums[0];
        while (head != turtle) {
            head = nums[head];
            turtle = nums[turtle];
        }
        return head;
    }
}

Notes

The second node traversal should be head != turtle instead of while True, and break if equal. This is for the edge case the first node is the duplicate.

Diagram

Decode Ways

LeetCode

Problem

Given a mapping ‘1’ -> ‘A’ to ‘26’ -> ‘Z’, and a string of numbers, find the number of ways to build characters.

Techniques

Dynamic Programming Recursion

Complexity

Time: O(N) go through each character in s Space: O(N) create an Dynamic Programming Cache

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        # 1. Can use dynamic programming solve the subproblems 
        # of number of ways up to the subword of using n characters
        # need to go backwards for case of 0 (10)
        # 55 -> 2 0 1
        # 0 1
        subwordNumWays = [0 for _ in range(len(s) + 1)]
        subwordNumWays[len(s)] = 1
        idx = len(s) - 1
        # 2. Handle for case 10 and 20
        if int(s[idx]) == 0:
            subwordNumWays[idx] = 0
        else:
            subwordNumWays[idx] = 1
        idx -= 1
        # 3. go through subproblems until all characters
        while idx >= 0:
            if int(s[idx]) == 0:
                # 4. Handle the case for 10 and 20
                idx -= 1
            else:
                # 5. if a number is 1 to 9 or 2[and something] add all ways up to it
                subwordNumWays[idx] += subwordNumWays[idx + 1]
                if int(s[idx:idx + 2]) <= 26:
                    # 6. add up ways for number 21 to 26
                    subwordNumWays[idx] += subwordNumWays[idx + 2]
                idx -= 1
        # 6. return num ways using all characters
        return subwordNumWays[0]

Java

class Solution {
    public int numDecodings(String s) {
        // 1. Create a dynamic programming cache working backwards to account for 0
        // for 10 or 20. All numbers up to i. Add + 1 for extra case of a two digit number base case
        int[] subNumDecodings = new int[s.length() + 1];
        // 2. 2 digit number base case
        subNumDecodings[s.length()] = 1;
        // 3. If the last digit is '0', the only base case is the two digit base case
        // Else another number 1 to 9 fits the 1 digit base case
        if (s.charAt(s.length() - 1) == '0') {
            subNumDecodings[s.length() - 1] = 0;
        } else {
            subNumDecodings[s.length() - 1] = 1;
        }
        
        // 4. Go backwards solve the subproblems of using all elements up to index
        for (int idx = s.length() - 2; idx >= 0; idx--) {
            // 5. if it is a 0, let the two digit case handle it in the next subproblem
            if (s.charAt(idx) == '0') {
                continue;
            }
            // 6. We know the number is not 0 so both can be two digit and just one digit have the
            // one digit case.
            subNumDecodings[idx] = subNumDecodings[idx + 1];
            // 7. Add the two digit subproblem case.
            if (Integer.parseInt(s.substring(idx, idx + 2)) <= 26) {
                subNumDecodings[idx] += subNumDecodings[idx + 2];
            }
        }
        // 8. Return master problem of using all digits
        return subNumDecodings[0];
    }
}

Notes

Have to go backward for ‘0’ case. Skip the case and let the next subproblem with two digits solve it.

Word Search II

LeetCode

Problem

Given a 2d array of words and a list of words, return a list of every word in the array up down left right.

Techniques

Recursion Search Trees

Complexity

Time: O(m * n)

Space: (w) Longest word?

Python

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # 1. Build a trie to efficiently see if a word is used
        trie = self.build_trie(words)
        # 3. Have a 2d for loop to traverse the board
        found = []
        for row in range(len(board)):
            for col in range(len(board[0])):
                # 4. from this row, col search to see if has a word.
                found.extend(self.trie_search(trie, board, row, col))
        # 5. return all found words remove duplicates
        return list(set(found))
                
    
    def build_trie(self, words):
        trie = {}
        # 2. Go through each word, and create a new dictionary for each leter
        # At the end, have the null char '\0' so we know word is done
        for word in words:
            level = trie
            for char in word:
                if char not in level:
                    level[char] = {}
                level = level[char]
            # level is at the end
            level['\0'] = word
        return trie
    
    def trie_search(self, level, board, row, col):
        # 5. check search is still in board
        if row < 0 or row >= len(board):
            return []
        if col < 0 or col >= len(board[0]):
            return []
        # 6. see in the character is in the level
        char = board[row][col]
        if char in level:
            # 7. see in the word is in the tire
            level = level[char]
            found = []
            if '\0' in level:
                found.append(level['\0'])
            # search left, right, up, down remove char and put back to not reuse in search
            board[row][col] = '#'
            found.extend(self.trie_search(level, board, row - 1, col))
            found.extend(self.trie_search(level, board, row + 1, col))
            found.extend(self.trie_search(level, board, row, col - 1))
            found.extend(self.trie_search(level, board, row, col + 1))
            board[row][col] = char
            return found
        else:
            return []

Java

Too Complicated :(

Notes

Minimum Window Substring

LeetCode

Problem

Given a string S and a string T, give the smallest window (continuous substring) of S that has all the characters of T

Techniques

Sliding Window

Complexity

Time: O(N) Go through S, at most twice for left and right pointers.

Space: O(N + M) need a dict for both S and T.

Python

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 1. Use a sliding window. Have a counter for number of characters in T.
        counterT = {} # or collections.Counter
        for char in t:
            if char in counterT:
                counterT[char] += 1
            else:
                counterT[char] = 1
        # 2. counter for S; all the characters in S used
        counterS = {}
        # 3. Have a left and right pointer for the start and end of the sliding window.
        ptr_left = 0
        ptr_right = 0
        # 4. Have a  set of characters in both S and T
        recorded_chars = set()
        # 5. Have a result length of infinity in case there is no solution
        result_length = float('inf')
        while ptr_right < len(s):
            char = s[ptr_right]
            # 6. Count char count in S
            if char in counterS:
                counterS[char] += 1
            else:
                counterS[char] = 1
            # 6. Check that is a required character and we stil need more of that character
            if char in counterT and counterT[char] <= counterS[char]:
                recorded_chars.add(char)
                # 7. while we have all characters we need, shrink sliding window on left
                while len(recorded_chars) == len(counterT):
                    # 8. remove the left most character counted
                    char_left = s[ptr_left]
                    counterS[char_left] -= 1
                    # 9. we used all of the characters of char_left needed
                    # this is a possible window
                    if char_left in counterT and counterT[char_left] > counterS[char_left]:
                        recorded_chars.remove(char_left)
                        # 10. get the end and start result if this is the best seen so far.
                        # +1 because we haven't incremented yet
                        if result_length > ptr_right - ptr_left + 1:
                            end = ptr_right
                            start = ptr_left
                            result_length = ptr_right - ptr_left + 1
                    ptr_left += 1
            ptr_right += 1

        # 11. if the result length is still infinity, return '' no solution
        if result_length == float('inf'):
            return ''
        # 12. return the window with the smallest start to end
        return s[start:end+1]

Java

class Solution {
    public String minWindow(String s, String t) {
        // 1. Create a counter for T
        Map<Character, Integer> counterT = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char charT = t.charAt(i);
            if (!counterT.containsKey(charT)) {
                counterT.put(charT, 0);
            }
            counterT.put(charT, counterT.get(charT) + 1);
        }
        // 2. Have a counter for S
        Map<Character, Integer> counterS = new HashMap<>();
        // 3. Have a left and right pointer
        int leftPtr = 0;
        int rightPtr = 0;
        // 4. Have a set for characters used in S and T
        Set<Character> recordedChars = new HashSet<>();
        // 5. Have resultLength initialized MAX_VALUE for 
        int resultLength = Integer.MAX_VALUE;
        // 6. increment rightPtr, expanding characters used
        int start = 0;
        int end = 0;
        while (rightPtr < s.length()) {
            char charS = s.charAt(rightPtr);
            if (!counterS.containsKey(charS)) {
                counterS.put(charS, 0);
            }
            counterS.put(charS, counterS.get(charS) + 1);

            // 7. check that character is required and we have enough
            if (counterT.containsKey(charS) && counterT.get(charS) <= counterS.get(charS)) {
                // 8. add it the set of characters used
                recordedChars.add(charS);
                while (recordedChars.size() == counterT.size()) {
                    // 9. Remove the left most character
                    char charLeft = s.charAt(leftPtr);
                    counterS.put(charLeft, counterS.get(charLeft) - 1);
                    if (counterT.containsKey(charLeft) && counterT.get(charLeft) > counterS.get(charLeft)) {
                        recordedChars.remove(charLeft);
                        if (resultLength > rightPtr - leftPtr + 1) {
                            end = rightPtr;
                            start = leftPtr;
                            resultLength = rightPtr - leftPtr + 1;
                        }  
                    }
                    leftPtr += 1;
                }
            }
            rightPtr++;
        }
        if (resultLength == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(start, end + 1);
    }
}

Notes

Post by: Brian T. Liao