>Digital-flame

interesting approach

// https://leetcode.com/problems/longest-nice-substring/
class Solution {
    public String longestNiceSubstring(String s) {
        int [] index = longestNiceSubstring(s, 0, s.length());
        return s.substring(index[0], index[1]);
    }

    private int [] longestNiceSubstring(String s, int start, int end) {
        for(int i = start; i < end; i++) {
            char ch = s.charAt(i);
            if(Character.isLowerCase(ch) && s.substring(start, end).contains(Character.toUpperCase(ch) + "")) continue;
            else if(Character.isUpperCase(ch) && s.substring(start, end).contains(Character.toLowerCase(ch) + "")) continue;

            int [] first = longestNiceSubstring(s, start, i);
            int [] second = longestNiceSubstring(s, i + 1, end);

            if(first[1] - first[0] >= second[1] - second[0]) {
                return first;
            } else {
                return second;
            }
        }

        return new int[] {start, end};
    }
}

classic sliding window

        int i = 0;
        int j = k;
        while (j < nums.length) {
            // do smth
            i++;
            j++;
        }

expanding sliding window example

package org.example;


import java.util.HashMap;

/**
 * https://leetcode.com/problems/maximum-length-substring-with-two-occurrences/description/
 */
public class Main {
    public static void main(String[] args) {
        maximumLengthSubstring("bcbbbcba");
    }

    public static int maximumLengthSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            map.clear();
            int jMax = i + 1;
            for (int j = i + 1; j < s.length(); j++) {
                if (map.containsKey(s.charAt(j)) && map.get(s.charAt(j)) == 2) {
                    break;
                }
                jMax = j;
                map.put(s.charAt(j), map.getOrDefault(s.charAt(j), 0) + 1);
            }
            // sliding window jMax - i here
            max = Math.max(max, jMax - i);
        }
        return max;
    }
}

if we have an array that we have to iterate circularily, we can double that array to avid corner cases

package org.example;


/**
 * https://leetcode.com/problems/alternating-groups-i/description/
 */
public class Main {
    public static void main(String[] args) {
        numberOfAlternatingGroups(new int[]{0, 1, 0, 0, 1});
    }

    public static int numberOfAlternatingGroups(int[] colors) {
        int n = colors.length;
        int[] doubleColours = new int[2 * n];
        for (int i = 0; i < n; i++) {
            doubleColours[i] = colors[i];
            doubleColours[i + n] = colors[i];
        }
        int start = 0;
        int i = start;
        int j = i + 2;
        int res = 0;
        while (true) {
            if (doubleColours[i] == doubleColours[j] && doubleColours[i] != doubleColours[i + 1]) {
                res++;
            }
            i++;
            j++;
            if (i == start + n) {
                break;
            }
        }
        return res;
    }
}

example

852. Peak Index in a Mountain Array

package org.example;


/**
 * https://leetcode.com/problems/peak-index-in-a-mountain-array/
 */
public class Main {
    public static void main(String[] args) {

    }

    public int peakIndexInMountainArray(int[] arr) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < arr[mid + 1]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

}

from comments on leetcode

mid = (start+end)/2 could result in integer overflow.
mid = start + (end-start)/2 could also result in integer overflow if the start and end are two extreme numbers.
The best way to handle this is to use
mid = end - (end - start) / 2;

example

package org.example;


/**
 * https://leetcode.com/problems/maximum-number-of-words-you-can-type/description/
 */
public class Main {
    public static void main(String[] args) {
        canBeTypedWords("leet code", "lt");
    }

    public static int canBeTypedWords(String text, String brokenLetters) {
        String[] words = text.split(" ");

        int count = words.length;
        for (int i = 0; i < words.length; i++) {
            for (char c : brokenLetters.toCharArray()) {
                int mask = getBitMask(words[i]);
                int bitNum = 1 << (c - 'a');
                if (hasBit(mask, bitNum)) {
                    count--;
                    break; // this word is excluded
                }
            }
        }
        return count;
    }

    private static boolean hasBit(int mask, int bitNumber) {
        return (mask & bitNumber) == bitNumber;
    }

    private static int getBitMask(String word) {
        int mask = 0;
        for (char c : word.toCharArray()) {
            mask |= 1 << (c - 'a');
        }
        return mask;
    }
}

Let’s say we have smth in range [1..32] || [1..64], so we can write that smth to the corresponding bit like this

int mask = 0;
mask |= 1 << 2; // 0001, last significant bit (LSB) will be shifted to 2 positions left and will result in 0100

example from leetcode

package org.example;


/**
 * https://leetcode.com/problems/count-pairs-of-similar-strings/description/
 */
public class Main {
    public static void main(String[] args) {

    }

    public int similarPairs(String[] words) {
        int[] masks = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            masks[i] = getMask(words[i]);
        }

        int countSimilar = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (masks[i] == masks[j]) {
                    countSimilar++;
                }
            }
        }
        return countSimilar;
    }

    private int getMask(String s) {
        int mask = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            mask |= 1 << (s.charAt(i) - 'a');
        }
        return mask;
    }
}

example

package org.example;


import java.util.PriorityQueue;

/**
 * https://leetcode.com/problems/matrix-cells-in-distance-order/description/
 */
public class Main {
    public static void main(String[] args) {
        allCellsDistOrder(2, 2, 0, 1);
    }

    private static int rowCount;
    private static int colCount;
    private static boolean[][] visited;

    public static int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        rowCount = rows;
        colCount = cols;
        visited = new boolean[rowCount][colCount];
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) ->
                x.getDistance() - y.getDistance()
        );

        Node root = new Node(rCenter, cCenter);

        dfs(root, root, pq);

        int[][] result = new int[pq.size()][2];
        int i = 0;
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            result[i++] = new int[]{node.getRow(), node.getCol()};
        }
        return result;
    }

    private static void dfs(Node root, Node node, PriorityQueue<Node> pq) {
        if (isOutOfBounds(node) || isVisited(node)) {
            return;
        }

        int distanceFromRoot = Math.abs(root.getRow() - node.getRow()) + Math.abs(root.getCol() - node.getCol());
        node.setDistance(distanceFromRoot);
        pq.add(node);
        visited[node.getRow()][node.getCol()] = true;

        // up
        dfs(root, new Node(node.getRow() - 1, node.getCol()), pq);
        // bottom
        dfs(root, new Node(node.getRow() + 1, node.getCol()), pq);
        // left
        dfs(root, new Node(node.getRow(), node.getCol() - 1), pq);
        // right
        dfs(root, new Node(node.getRow(), node.getCol() + 1), pq);
    }

    private static boolean isVisited(Node node) {
         return visited[node.getRow()][node.getCol()];
    }

    private static boolean isOutOfBounds(Node node) {
        boolean isRowsOutOfBounds = node.getRow() < 0 || node.getRow() > rowCount - 1;
        boolean isColsOutOfBounds = node.getCol() < 0 || node.getCol() > colCount - 1;
        return isRowsOutOfBounds || isColsOutOfBounds;
    }
}

class Node {
    private int row;
    private int col;
    private int distance;

    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public int getDistance() {
        return distance;
    }

    public void setDistance(int distance) {
        this.distance = distance;
    }
}

example

package org.example;


/**
 * https://leetcode.com/problems/island-perimeter/description/
 */
public class Main {
    public static void main(String[] args) {

    }

    private final int VISITED = -1;
    private final int ISLAND = 1;
    private final int WATER = 0;

    public int islandPerimeter(int[][] grid) {
        int perimeter = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == ISLAND) {
                    perimeter = perimeter + dfs(grid, i, j);
                }
            }
        }
        return perimeter;
    }

    private int dfs(int[][] grid, int row, int col) {
        if (isOutOfBounds(grid, row, col) || grid[row][col] == WATER) {
            return 1;
        }
        if (grid[row][col] == VISITED) {
            return 0;
        }
        grid[row][col] = VISITED;

        return dfs(grid, row + 1, col) + dfs(grid, row - 1, col)
                + dfs(grid, row, col - 1) + dfs(grid, row, col + 1);
    }

    private boolean isOutOfBounds(int[][] grid, int row, int col) {
        boolean rows = row < 0 || row > grid.length - 1;
        boolean cols = col < 0 || col > grid[0].length - 1;
        return rows || cols;
    }
}

example

package org.example;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * https://leetcode.com/problems/01-matrix/description/
 */
public class Main {
    public static void main(String[] args) {
        int[][] mat = new int[][]{{0, 1, 1, 1, 1}, {1, 1, 1, 1, 0}};
        updateMatrix(mat);
    }

    /**
     * DFS Approach, gives TLE, but works anyway
     *
     * @param mat
     * @return
     */
    public static int[][] updateMatrix(int[][] mat) {
        Queue<Node> roots = new LinkedList<>();
        collectRoots(mat, roots);

        int[][][] tempAnswers = new int[roots.size()][][];
        int i = 0;
        while (!roots.isEmpty()) {
            Node root = roots.poll();
            int[][] ansMatrix = new int[mat.length][mat[0].length];
            for (int j = 0; j < ansMatrix.length; j++) {
                Arrays.fill(ansMatrix[j], Integer.MAX_VALUE);
            }
            tempAnswers[i++] = ansMatrix;
            dfs(root, root, ansMatrix);
        }

        int[][] finalAnswers = new int[mat.length][mat[0].length];
        for (int r = 0; r < mat.length; r++) {
            for (int c = 0; c < mat[0].length; c++) {
                finalAnswers[r][c] = getMinValue(tempAnswers, r, c);
            }
        }
        return finalAnswers;
    }

    private static int getMinValue(int[][][] mat, int row, int col) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < mat.length; i++) {
            if (mat[i][row][col] < min) {
                min = mat[i][row][col];
            }
        }
        return min;
    }

    private static void dfs(Node root, Node node, int[][] ansMatrix) {
        if (isOutOfBounds(node, ansMatrix)) {
            return;
        }
        boolean isVisited = ansMatrix[node.row()][node.col()] != Integer.MAX_VALUE;
        if (isVisited) {
            return;
        }

        int dist = Math.abs(root.row() - node.row()) + Math.abs(root.col() - node.col());
        ansMatrix[node.row()][node.col()] = dist;

        // spread in 4 directions, because we are in matrix and each cell like a node
        // right
        dfs(root, new Node(node.row(), node.col() + 1), ansMatrix);
        // left
        dfs(root, new Node(node.row(), node.col() - 1), ansMatrix);
        // top
        dfs(root, new Node(node.row() - 1, node.col()), ansMatrix);
        // bottom
        dfs(root, new Node(node.row() + 1, node.col()), ansMatrix);

    }

    private static void collectRoots(int[][] mat, Queue<Node> q) {
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 0) {
                    q.add(new Node(i, j));
                }
            }
        }
    }

    private static boolean isOutOfBounds(Node node, int[][] matrix) {
        boolean outRow = node.row() > matrix.length - 1 || node.row() < 0;
        boolean outCol = node.col() > matrix[0].length - 1 || node.col() < 0;
        return outRow || outCol;
    }

}

record Node(int row, int col) {
}