# 20210522

[Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

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
        v
"abcabcbb"
        ^
 map {a : 3,
      b : 7,
      c : 5}
 result = 3
      
      
     v  
  "dvdf"
    ^
  {d : 0,
   v : 1}

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0)
        return 0;
    
    Map<Character, Integer> map = new HashMap<>();
    int result = 0;
    int windowStart = 0;
    // "abcabcbb"
    for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
        char c = s.charAt(windowEnd); // a
        if (map.contains(c)) {
            windowStart = Math.max(windowStart, map.get(c) + 1); // 1
        }
        map.put(c, windowEnd); // {a: , b : 1, c: 2}
        result = Math.max(result, windowEnd - windowStart + 1); // 3
    }
    
    return result;
}

62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

m = 2, n = 2
1 1
1 2

m = 3, n = 4
1 1 1 1
1 2 3 4
1 3 6 10

m * n


public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
        dp[0][i] = 1;
    }
    
    Arrays.fill(dp, 1);
//     m = 3, n = 4
//     1 1 1 1
//     1 2 3 
//     1 

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    
    return dp[m - 1][n - 1];
}

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Input: p = [1,2,3], q = [1,2,3]
Output: true

Input: p = [1,2], q = [1,null,2]
Output: false

            isSameTree(1, 1) True
             /         \
True isSameTree(2, 2)    isSameTree(3, 3) True    

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null)
        return true;
    
    if (p == null || q == null)
        return false;
        
    if (p.val != q.val)
        return false;
        
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}