## Keys and Rooms

``````class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int n = rooms.size();
boolean[] visited = new boolean[n];
Queue<Integer> q = new LinkedList<>();
visited[0] = true;
for(int nn : rooms.get(0)){
}
while(!q.isEmpty()){
int t = q.poll();
if(!visited[t]){
visited[t] = true;
for(int nn : rooms.get(t))
}
}
for(boolean b : visited)
if(!b)
return false;
return true;
}
}``````

## Custom Sort String

``````class Solution {
public String customSortString(String order, String s) {
Map<Character, Integer> m = new HashMap<>();
int k = 100;
for(char c : order.toCharArray())
m.put(c, k--);
List<Character> list = new ArrayList<>();
for(char c : s.toCharArray())
Collections.sort(list, (a,b) ->{
int aa = m.getOrDefault(a, Integer.MAX_VALUE / 2);
int bb = m.getOrDefault(b, Integer.MAX_VALUE / 2);
return bb - aa;
});
StringBuilder sb = new StringBuilder();
for(char c : list)
sb.append(c);
return sb.toString();
}
}``````

## Projection Area of 3D Shapes

``````class Solution {
public int projectionArea(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int xy = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++){
if(grid[i][j] != 0)
xy++;
}
}
int xz = 0;
for(int i = 0; i < n; i++) {
int max = 0;
for(int j = 0; j < m; j++){
if(grid[i][j] != 0)
max = Math.max(max,grid[i][j]);
}
xz += max;
}
int zy = 0;
for(int j = 0; j < m; j++) {
int max = 0;
for(int i = 0; i < n; i++){
if(grid[i][j] != 0)
max = Math.max(max,grid[i][j]);
}
zy += max;
}
return xy + xz + zy;
}
}``````

## Partition Array for Maximum Sum

``````class Solution {
public int maxSumAfterPartitioning(int[] arr, int k) {
int n = arr.length;
int[] dp = new int[n + 1];
int res = 0;
for(int i = 0; i <= n; i++) {
int max = 0;
int t = Math.max(0, i - k);
for(int j = i - 1; t <= j; j--) {
max = Math.max(max, arr[j]);
dp[i] = Math.max(dp[i], dp[j] + max * (i - j)); // dp[i - 1] dp[i - 2]
}
}
return dp[n];
}
}``````

## Swap Adjacent in LR String

``````class Solution {
public boolean canTransform(String start, String end) {
int i = 0;
int j = 0;
int n = start.length();
int m = end.length();
while(i < n && j < m){
if(start.charAt(i) == 'X'){
i++;
}else if(end.charAt(j) == 'X'){
j++;
}else{ // no X
if(start.charAt(i) != end.charAt(j))
return false;
if(start.charAt(i) == 'R' && i > j)
//  s[i] == e[j]   start = xxR (i == 2) end = xRx (i == 1)
return false;
if(start.charAt(i) == 'L' && i < j)
//  s[i] == e[j]  start = xLx (i == 1) end = xxL (i == 2)
return false;
i++;
j++;
}
}
while(i < n){
if(start.charAt(i) != 'X') // xxxxLRLRLxxxxxL false
return false;
i++;
}
while(j < m){
if(end.charAt(j) != 'X')
return false;
j++;
}
return true;
}
}``````

## Encode Number

``````class Solution {
public String encode(int num) {
return Integer.toBinaryString(num + 1).substring(1);
}
}``````

## Count Substrings That Differ by One Character

``````class Solution {
public int countSubstrings(String s, String t) {
int n = s.length();
int m = t.length();
int[][] allMatch = new int[n][m]; // # of substring all match for s and t untill i,j
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j < t.length(); j++) {
boolean ma = s.charAt(i) == t.charAt(j);
if(i == 0 || j == 0){
if(ma){
allMatch[i][j] = 1;
}
}
else
{
if(ma){
allMatch[i][j] = allMatch[i - 1][j - 1] + 1;
}
else{
allMatch[i][j] = 0;
}
}
}
}
int[][] missOne = new int[n][m];
int res = 0;
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j < t.length(); j++) {
boolean ma = s.charAt(i) == t.charAt(j);
if(i == 0 || j == 0){
if(!ma){
missOne[i][j] = 1;
}
}
else
{
if(ma){
missOne[i][j] = missOne[i - 1][j - 1];
}
else{
missOne[i][j] = allMatch[i - 1][j - 1] + 1;
}
}
res += missOne[i][j];
}
}
return res;
}
}``````

## Detect Squares

``````class DetectSquares {
int[][] g = new int[1001][1001];
public DetectSquares() {

}

public void add(int[] point) {
g[point[0]][point[1]]++;
}

public int count(int[] point) {
int res = 0;
for(int i = 0; i < 1001; i++){
if(Math.abs(point[0] - i) > 0){
int j1 = point[1] + Math.abs(point[0] - i);
if(0 <= j1 && j1 <= 1000){
res += g[i][j1] * g[i][point[1]] * g[point[0]][j1];
}
int j2 = point[1] - Math.abs(point[0] - i);
if(0 <= j2 && j2 <= 1000){
res += g[i][j2] * g[i][point[1]] * g[point[0]][j2];
}
}
}
return res;
}
}

/**
* Your DetectSquares object will be instantiated and called as such:
* DetectSquares obj = new DetectSquares();
* int param_2 = obj.count(point);
*/``````

## Maximum Number of Points with Cost

``````class Solution {
public long maxPoints(int[][] points) {
int n = points.length;
int m = points[0].length;
long[][] dp = new long[n][m];
long res = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
long tmp = 0;
for(int k = 0; k < m; k++) {
if(i == 0)
{
tmp = points[i][j];
break;
}
else
{
tmp = Math.max(tmp, points[i][j] + dp[i - 1][k]- Math.abs(k - j));
}
}
dp[i][j] = tmp;
res = Math.max(res, dp[i][j]);
}
}
return res;
}
}``````

## Count Number of Maximum Bitwise-OR Subsets

``````class Solution {
int res = 0;
public int countMaxOrSubsets(int[] nums) {
int max = 0;
for(int n : nums)
max |= n;
dfs(nums, max, 0, 0);
return res;
}
public void dfs(int[] nums,int max,int tmp, int pos){
if(tmp == max)
res++;
if(pos >= nums.length)
return;
for(int i = pos; i < nums.length; i++){
int tt = tmp;
dfs(nums, max, tmp | nums[i], i+1);
tmp = tt;
}
}
}``````