# 1170. Compare Strings by Frequency of the Smallest Character

Let’s define a function `f(s)` over a non-empty string `s`, which calculates the frequency of the smallest character in `s`. For example, if `s = "dcce"` then `f(s) = 2` because the smallest character is `"c"` and its frequency is 2.

Now, given string arrays `queries` and `words`, return an integer array `answer`, where each `answer[i]` is the number of words such that `f(queries[i])` < `f(W)`, where `W` is a word in `words`.

Example 1:

Input:

``` queries = ["cbd"], words = ["zaaaz"]
```

Output:

``` [1]
```

Explanation:

``` On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").
```

Example 2:

Input:

``` queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
```

Output:

``` [1,2]
```

Explanation:

``` On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").
```

Constraints:

• `1 <= queries.length <= 2000`
• `1 <= words.length <= 2000`
• `1 <= queries[i].length, words[i].length <= 10`
• `queries[i][j]``words[i][j]` are English lowercase letters.

#### Straight forward solution O(q * w)

```class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int[] result = new int[queries.length];
for (int i = 0 ; i < queries.length; i ++){
int score = s(queries[i]);

for (String w : words){
if (s(w) > score){
result[i] ++;
}
}
}
return result;
}

public static int s(String s) {
char min = 'z';
char[] ca = s.toCharArray();
for(char c : ca){
if (c < min){
min = c;
}
if (c == 'a'){
break;
}
}
int r = 0;
for(char c : ca){
if (c == min)
r ++;
}
return r;
}
}```

#### Optimized solution O (q + w)

since we have `1 <= queries[i].length, words[i].length <= 10`

which means query will have only 10 possible values (limited), so for the result.

so we can use counting.

```class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {

int[] freqCounter = new int[11];
int[] result = new int[queries.length];
for (int i = 0; i < words.length; i++) {
int freq = s(words[i]);
freqCounter[freq]++;
}

for (int i = 1; i < freqCounter.length; i++) {
freqCounter[i] += freqCounter[i - 1];
}
for (int i = 0; i < queries.length; i++) {
int freq = s(queries[i]);
result[i] = words.length - freqCounter[freq];
}

return result;
}

public static int s(String s) {
char min = 'z';
int r = 0;
char[] ca = s.toCharArray();
for(char c : ca){
if (c < min){
r = 1;
min = c;
} else if(c == min) {
r ++;
}

}
return r;
}

}```

# 1278. Palindrome Partitioning III

You are given a string `s` containing lowercase letters and an integer `k`. You need to :

• First, change some characters of `s` to other lowercase English letters.
• Then divide `s` into `k` non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input:

``` s = "abc", k = 2
```

Output:

``` 1
```

Explanation:

``` You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.
```

Example 2:

Input:

``` s = "aabbc", k = 3
```

Output:

``` 0
```

Explanation:

` You can split the string into "aa", "bb" and "c", all of them are palindrome.`

Example 3:

Input:

``` s = "leetcode", k = 8
```

Output:

``` 0
```

Constraints:

• `1 <= k <= s.length <= 100`.
• `s` only contains lowercase English letters.

Failed to build the dp during the contest : ( .   it was quite close

```class Solution {
public int palindromePartition(String s, int k) {
if (k == s.length()){
return 0;
}

int[][] dp = new int[s.length()+1][k+1];

for (int i = 0; i <= s.length(); i++)
for (int j = 0; j <= k; j++)
dp[i][j] = s.length();

dp[0][0] = 0;
for (int i = 0; i < s.length(); i ++){

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

for (int len = 1; i + len <= s.length(); len++) {
int cost = 0;

for (int a = i, b = i + len - 1; a < b; a++, b--){
if (s.charAt(a) != s.charAt(b)){
cost ++;
}
}

dp[i + len][j + 1] = Math.min(dp[i + len][j + 1], dp[i][j] + cost);
}
}
}

return dp[s.length()][k];
}

}```

Few things to point out:

• I initialize each value of dp with s.length(), since it can’t be worse than replacing every chars. Integer.MAX_VALUE will cause an integer overflow while building the dp

# 1277. Count Square Submatrices with All Ones

Given a `m * n` matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input:

``` matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
```

Output:

``` 15
```

Explanation:

```
There are 10 squares of side 1.
There are 4 squares of side 2.
There is one square of side 3.
Total number of squares = 10 + 4 + 1 = 15

```

Example 2:

Input:

``` matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
```

Output:

``` 7
```

Explanation:

```
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7```

Constraints:

• `1 <= arr.length <= 300`
• `1 <= arr[0].length <= 300`
• `0 <= arr[i][j] <= 1`

Example:

[0,1,1,1],
[1,1,1,1],
[0,1,1,1]

1. count single ones
2. count 2×2
3. count 3×3
4. ……

Goal: reduce n x n to (n-1)x(n-1) … to 2×2

Now scan 2×2 block, for each position(i,j) scan (i+1,j) (i,j+1) (i+1, j+1)
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]

if the 2×2 scanning block contains 0, update (i,j) to 0
[0,1,1,1],
[0,1,1,1],
[0,1,1,1]

then we can reduce it by removing (ignoring) the last row and column.

[0,1,1],
[0,1,1]

Then walk through with the 2×2 scanning block again.

the counter could be updated when the whole 2×2 block is 1, OR count number of ones in the next round.

Version A, update counter during 2×2 scan

```class Solution {
public int countSquares(int[][] matrix) {
int c = 0;

int m  = matrix.length;
int n  = matrix[0].length;

for (int i = 0; i < m; i ++){
for (int j = 0; j < n; j ++){
if (matrix[i][j] == 1){
c++;
}
}
}

while (m > 1 && n > 1){
for (int i = 0; i < m-1; i ++){
for (int j = 0; j < n-1; j ++){
if (  matrix[i][j]     == 0
|| matrix[i+1][j]   == 0
|| matrix[i][j+1]   == 0
|| matrix[i+1][j+1] == 0)
{
matrix[i][j] = 0;
}  else {
c++;
}
}
}
// lower m and n (ignoring last row and column)
m --;
n --;
}
return c;

}
}```

B, a more compact version, update counter next round, count number of ones.
slightly slower for more loops

```class Solution {
public int countSquares(int[][] matrix) {
int c = 0;

int m  = matrix.length;
int n  = matrix[0].length;

while (m > 0 && n > 0){

for (int i = 0; i < m; i ++){
for (int j = 0; j < n; j ++){
if (matrix[i][j] == 1){
c++;
}
}
}

for (int i = 0; i < m-1; i ++){
for (int j = 0; j < n-1; j ++){
if (matrix[i][j] == 0
|| matrix[i+1][j] == 0
|| matrix[i][j+1] == 0
|| matrix[i+1][j+1] == 0){
matrix[i][j] = 0;
}
}
}
// lower m and n (ignoring last row and column)
m --;
n --;
}
return c;

}
}```

A: 86-110 ms
B: 160-170 ms

# 1276. Number of Burgers with No Waste of Ingredients

Given two integers `tomatoSlices` and `cheeseSlices`. The ingredients of different burgers are as follows:

• Jumbo Burger: 4 tomato slices and 1 cheese slice.
• Small Burger: 2 Tomato slices and 1 cheese slice.

Return `[total_jumbo, total_small]` so that the number of remaining `tomatoSlices` equal to 0 and the number of remaining `cheeseSlices` equal to 0. If it is not possible to make the remaining `tomatoSlices` and `cheeseSlices` equal to 0 return `[]`.

Example 1:

Input:

``` tomatoSlices = 16, cheeseSlices = 7
```

Output:

``` [1,6]
```

Explantion:

``` To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese. There will be no remaining ingredients.
```

Example 2:

Input:

``` tomatoSlices = 17, cheeseSlices = 4
```

Output:

``` []
```

Explantion:

``` There will be no way to use all ingredients to make small and jumbo burgers.
```

Example 3:

Input:

``` tomatoSlices = 4, cheeseSlices = 17
```

Output:

``` []
```

Explantion:

``` Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.
```

Example 4:

Input:

``` tomatoSlices = 0, cheeseSlices = 0
```

Output:

``` [0,0]
```

Example 5:

Input:

``` tomatoSlices = 2, cheeseSlices = 1
```

Output:

``` [0,1]
```

Constraints:

• `0 <= tomatoSlices <= 10^7`
• `0 <= cheeseSlices <= 10^7`

Should be an easy question..

```class Solution {
public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {

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

if (tomatoSlices % 2 ==1 || cheeseSlices * 4 < tomatoSlices || cheeseSlices * 2 > tomatoSlices){
return result;
}

int x = (tomatoSlices - cheeseSlices*2)/2;

return result;
}
}```

# 1275. Find Winner on a Tic Tac Toe Game

Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

• Players take turns placing characters into empty squares (” “).
• The first player A always places “X” characters, while the second player B always places “O” characters.
• “X” and “O” characters are always placed into empty squares, never on filled ones.
• The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Given an array `moves` where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return “Draw”, if there are still movements to play return “Pending”.

You can assume that `moves` is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example 1:

Input:

``` moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
```

Output:

``` "A"
```

Explanation:

``` "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "```

X

```  "
"   " -> "   " -> " X " -> " X " -> "```

X

``` "
"   "    "O  "    "O  "    "OO "    "OO```

X

```"
```

Example 2:

Input:

``` moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
```

Output:

``` "B"
```

Explanation:

``` "B" wins.
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XX```

O

```"
"   " -> " O " -> " O " -> " O " -> "XO " -> "X```

O

``` "
"   "    "   "    "   "    "   "    "   "    "```

O

```  "
```

Example 3:

Input:

``` moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
```

Output:

``` "Draw"
```

Explanation:

``` The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"
```

Example 4:

Input:

``` moves = [[0,0],[1,1]]
```

Output:

``` "Pending"
```

Explanation:

``` The game has not finished yet.
"X  "
" O "
"   "
```

Constraints:

• `1 <= moves.length <= 9`
• `moves[i].length == 2`
• `0 <= moves[i][j] <= 2`
• There are no repeated elements on `moves`.
• `moves` follow the rules of tic tac toe.
```class Solution {
public String tictactoe(int[][] moves) {

for (int a = 0; a <= 1; a++ ){
int[] x = new int[3];
int[] y = new int[3];
int[] v = new int[2];

for (int i = a ; i < moves.length; i += 2){
x[moves[i][0]] ++;
y[moves[i][1]] ++;
if (moves[i][0] == moves[i][1]){
v[0] ++;
}
if (moves[i][0] == 2 - moves[i][1]) {
v[1] ++;
}
}

if (x[0] == 3 || x[1] == 3 ||x[2] == 3 || y [0] == 3 || y [1] == 3|| y [2] == 3 || v[0] == 3 || v[1] == 3){
return a==0? "A":"B";
}
}

return moves.length == 9? "Draw":"Pending";
}
}```

# 1269. Number of Ways to Stay in the Same Place After Some Steps

You have a pointer at index `0` in an array of size `arrLen`. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place  (The pointer should not be placed outside the array at any time).

Given two integers `steps` and `arrLen`, return the number of ways such that your pointer still at index `0` after exactly `steps` steps.

Since the answer may be too large, return it modulo `10^9 + 7`.

Example 1:

Input:

``` steps = 3, arrLen = 2
```

Output:

``` 4
```

Explanation:

```There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay
```

Example 2:

Input:

``` steps = 2, arrLen = 4
```

Output:

``` 2
```

Explanation:

``` There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay
```

Example 3:

Input:

``` steps = 4, arrLen = 2
```

Output:

``` 8
```

Constraints:

• `1 <= steps <= 500`
• `1 <= arrLen <= 10^6`

```class Solution {
public int numWays(int steps, int arrLen) {
int end = Math.min(steps, arrLen);

int mod = 1000000000 + 7;
long[][] dp = new long[steps+1][end+5];

dp[0][0] = 1;

for (int i = 0; i < steps; i++) {
dp[i+1][0] = (dp[i][0] + dp[i][1]) % mod;
for (int j = 1; j < end; j++) {
dp[i+1][j] = (dp[i][j-1] + dp[i][j] + dp[i][j+1]) % mod;
}
}
return (int) (dp[steps][0]);
}
}```

# 1268. Search Suggestions System

Given an array of strings `products` and a string `searchWord`. We want to design a system that suggests at most three product names from `products` after each character of `searchWord` is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested `products` after each character of `searchWord` is typed.

Example 1:

Input:

``` products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
```

Output:

``` [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
]
```

Explanation:

``` products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]
```

Example 2:

Input:

``` products = ["havana"], searchWord = "havana"
```

Output:

``` [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
```

Example 3:

Input:

``` products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
```

Output:

``` [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
```

Example 4:

Input:

``` products = ["havana"], searchWord = "tatiana"
```

Output:

``` [[],[],[],[],[],[],[]]
```

Constraints:

• `1 <= products.length <= 1000`
• `1 <= Σ products[i].length <= 2 * 10^4`
• All characters of `products[i]` are lower-case English letters.
• `1 <= searchWord.length <= 1000`
• All characters of `searchWord` are lower-case English letters.
```class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {

List<List<String>> r = new ArrayList<>();
Arrays.sort(products);

for (int i = 0; i < searchWord.length(); i ++){
List<String> rr = new ArrayList<>();
String prefix = searchWord.substring(0,i+1);

for (int j = 0; j < products.length && rr.size() < 3; j ++){
if(products[j].startsWith(prefix)){
}
}

}
return r;
}
}
```

Yes, we can introduce trie for more results. 3 is fairly small here

# 1267. Count Servers that Communicate

You are given a map of a server center, represented as a `m * n` integer matrix `grid`, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Example 1:

Input:

``` grid = [[1,0],[0,1]]
```

Output:

``` 0
Explanation: No servers can communicate with others.```

Example 2:

Input:

``` grid = [[1,0],[1,1]]
```

Output:

``` 3
Explanation: All three servers can communicate with at least one other server.
```

Example 3:

Input:

``` grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
```

Output:

``` 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.
```

Constraints:

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m <= 250`
• `1 <= n <= 250`
• `grid[i][j] == 0 or 1`
```class Solution {
public int countServers(int[][] grid) {
int result = 0 ;
int[] a = new int[grid.length];
int[] b = new int[grid[0].length];

for (int i = 0; i < grid.length; i ++){
for (int j = 0; j < grid[0].length; j ++){
if (grid[i][j] == 1){
a[i] ++;
b[j] ++;
result ++;
}
}
}

for (int i = 0; i < grid.length; i ++){
for (int j = 0; j < grid[0].length; j ++){
if (a[i] == 1 && b[j] == 1 && grid[i][j] == 1){
result --;
}
}
}

return result;
}

}```