Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

* Method 1: Brutal force TLE

```Java

class Solution {

public List<List<Integer>> palindromePairs(String[] words) {

int len = words.length;

List<List<Integer>> res = new ArrayList<>();

for(int i = 0; i < len; i++){

for(int j = 0; j < len; j++){

if(i == j) continue;

if(isPalindrome(words[i] + words[j])){

List<Integer> temp = new ArrayList<>();

temp.add(i);

temp.add(j);

res.add(temp);

}

}

}

return res;

}

private boolean isPalindrome(String s){

int left = 0, right = s.length() - 1;

char[] arr = s.toCharArray();

while(left < right){

if(arr[left++] != arr[right--])

return false;

}

return true;

}

}

```

* Method 2: HashMap O(N * K^2)

```Java

class Solution {

public List<List<Integer>> palindromePairs(String[] words) {

List<List<Integer>> res = new ArrayList<>();

if(words == null || words.length < 2) return res;

Map<String, Integer> map = new HashMap<>();

for(int i = 0; i < words.length; i++){ // O(N)

map.put(words[i], i);

}

for(int i = 0; i < words.length; i++){ // O(N * k)

for(int j = 0; j <= words[i].length(); j++){

String first = words[i].substring(0, j);

String second = words[i].substring(j);

if(isPalindrome(first)){ // O(k)

//first is palindrome, check if we have reverse of second

String reverse = new StringBuilder(second).reverse().toString();

if(map.containsKey(reverse) && map.get(reverse) != i){

List<Integer> temp = new ArrayList<>();

temp.add(map.get(reverse));

temp.add(i);

res.add(temp);

}

}

if(second.length() != 0 && isPalindrome(second)){ // O(k)

String reverse = new StringBuilder(first).reverse().toString();

if(map.containsKey(reverse) && map.get(reverse) != i){

List<Integer> temp = new ArrayList<>();

temp.add(i);

temp.add(map.get(reverse));

res.add(temp);

}

}

}

}

return res;

}

private boolean isPalindrome(String s){

int left = 0, right = s.length() - 1;

char[] arr = s.toCharArray();

while(left < right){

if(arr[left++] != arr[right--])

return false;

}

return true;

}

}

```

* Method 3: Tire Tree

```Java

class Solution {

private static class Node{

Node[] childs;

boolean isLeaf;

int index;

public Node(){

this.childs = new Node[26];

}

}

private Node root;

private void insert(String s, int index){

char[] arr = s.toCharArray();

Node temp = root;

for(int i = 0; i < arr.length; i++){

if(temp.childs[arr[i] - 'a'] == null){

temp.childs[arr[i] - 'a'] = new Node();

}

temp = temp.childs[arr[i] - 'a'];

}

temp.isLeaf = true;

temp.index = index;

}

private Node contains(String s){

char[] arr = s.toCharArray();

Node temp = root;

for(int i = 0; i < arr.length; i++){

if(temp.childs[arr[i] - 'a'] == null) return null;

temp = temp.childs[arr[i] - 'a'];

}

return temp;

}

public List<List<Integer>> palindromePairs(String[] words) {

this.root = new Node();

for(int i = 0; i < words.length; i++){

insert(words[i], i);

}

List<List<Integer>> result = new ArrayList<>();

for(int i = 0; i < words.length; i++){

for(int j = 0; j <= words[i].length(); j++){

String first = words[i].substring(0, j);

String second = words[i].substring(j);

if(isPalindrome(first)){

String reverse = new StringBuilder(second).reverse().toString();

Node temp = contains(reverse);

if(temp != null && temp.isLeaf && temp.index != i){

result.add(Arrays.asList(temp.index, i));

}

}

if(second.length() != 0 && isPalindrome(second)){

String reverse = new StringBuilder(first).reverse().toString();

Node temp = contains(reverse);

if(temp != null && temp.isLeaf && temp.index != i){

result.add(Arrays.asList(i, temp.index));

}

}

}

}

return result;

}

private boolean isPalindrome(String s){

int l = 0, r = s.length() - 1;

while(l < r){

if(s.charAt(l++) != s.charAt(r--)) return false;

}

return true;

}

}

```

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

* Method 1: HashMap

```Java

class Solution {

public List<Integer> findAnagrams(String s, String p) {

Map<Character, Integer> map = new HashMap<>();

for(char c : p.toCharArray()){

map.put(c, map.getOrDefault(c, 0) + 1);

}

int pLen = p.length(), sLen = s.length();

List<Integer> res = new ArrayList<>();

if(sLen < pLen) return res;

Map<Character, Integer> temp = new HashMap<>();

for(int i = 0; i < pLen; i++){

char c = s.charAt(i);

temp.put(c, temp.getOrDefault(c, 0) + 1);

}

for(int i = pLen; i <= sLen; i++){

if(check(temp, map)) res.add(i - pLen);

// Remove the first character

char first = s.charAt(i - pLen);

Integer count = temp.get(first);

if(count == 1) temp.remove(first);

else if(count != null) temp.put(first, count - 1);

if(i < sLen){

char c = s.charAt(i);

temp.put(c, temp.getOrDefault(c, 0) + 1);

}

}

return res;

}

private boolean check(Map<Character, Integer> map1, Map<Character, Integer> map2){

for(Map.Entry<Character, Integer> entry : map1.entrySet()){

if(!map2.containsKey(entry.getKey())) return false;

if(!map2.get(entry.getKey()).equals(entry.getValue())) return false;

}

return true;

}

}

```

Given a blacklist B containing unique integers from [0, N), write a function to return a uniform random integer from [0, N) which is NOT in B.

Optimize it such that it minimizes the call to system’s Math.random().

Note:

1. 1 <= N <= 1000000000

2. 0 <= B.length < min(100000, N)

3. [0, N) does NOT include N. See interval notation.

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has two arguments, N and the blacklist B. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.

* Method 1: TLE / MLE

```Java

class Solution {

private Set<Integer> black;

private int[] valid;

private Random random;

private int N;

private int size;

public Solution(int N, int[] blacklist) {

this.black = new HashSet<>();

for(int b : blacklist) this.black.add(b);

this.valid = new int[N - blacklist.length];

int count = 0;

for(int i = 0; i < N; i++){

if(this.black.contains(i)) continue;

this.valid[count++] = i;

}

this.size = this.valid.length;

this.random = new Random();

this.N = N;

}

public int pick() {

return this.valid[Math.abs(random.nextInt()) % size];

}

}

/**

```

* Method 2: reorder HashMap

1. We first create a hashtable for saving all blacklist.

2. we insert all the valid numbers to previous blacklist positions.

3. Use random to get a random value, if that value is in the map, we return the value, otherwise, we just return the value directly.

```Java

class Solution {

private Map<Integer, Integer> map;

private Random random;

private int M;

public Solution(int N, int[] blacklist) {

this.random = new Random();

this.map = new HashMap<>();

for(int b : blacklist){

map.put(b, -1);

}

this.M = N - blacklist.length;

N--;

for(int b : blacklist){

if(b < M){

while(map.containsKey(N)) N--;

map.put(b, N--);

}

}

}

public int pick() {

int next = random.nextInt(M);

return map.containsKey(next) ? map.get(next): next;

}

}

/**

```