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;
    }
    
}

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";
    }
}

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

• In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
• You have to visit the points in the same order as they appear in the array.

Example 1:

Input:

 points = [[1,1],[3,4],[-1,0]]

Output:

 7

Explanation:

One optimal path is

[1,1]

 -> [2,2] -> [3,3] ->

[3,4]

-> [2,3] -> [1,2] -> [0,1] ->

[-1,0]

   
Time from [1,1] to [3,4] = 3 seconds 
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds

Example 2:

Input:

 points = [[3,2],[-2,2]]

Output:

 5

Constraints:

• points.length == n
• 1 <= n <= 100
• points[i].length == 2
• -1000 <= points[i][0], points[i][1] <= 1000

class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int result = 0;
        int prev_x = points[0][0];
        int prev_y = points[0][1];
        for (int i = 1; i < points.length; i ++){
            int x = points[i][0];
            int y = points[i][1];
            
            int diff_x = Math.abs(x - prev_x);
            int diff_y = Math.abs(y - prev_y);
            
            result += Math.min(diff_x,diff_y)+Math.abs(diff_x-diff_y);
            
            prev_x = x;
            prev_y = y;
        }
        return result;
    }
}

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input:

[1,2,3,4,5,6,7] and

k

 = 3

Output:

[5,6,7,1,2,3,4]

Explanation:

rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input:

[-1,-100,3,99] and

k

 = 2

Output:

 [3,99,-1,-100]

Explanation:

 rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Note:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

In place rotate

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return NULL
     */
    function rotate(&$nums, $k) {
        $c = count($nums);
        $steps = 0;
        $start = 0;
        
        while($steps < $c){  
            $i = $start;
            $prev = $nums[$i];
            do{         
                $next = ($i+$k)%$c;
                $temp = $nums[$next];
                $nums[$next] = $prev;
                $prev = $temp;
                $i += $k;
                $i = $i % $c;
                $steps++;
            }while($start != $i);
            $start ++;
            
        }
    
    }
}

Given a string S, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

"ab-cd"

"dc-ba"

"a-bC-dEf-ghIj"

"j-Ih-gfE-dCba"

"Test1ng-Leet=code-Q!"

"Qedo1ct-eeLg=ntse-T!"

Straightforward solution. 

1. collect letters in reverse order.
2. go through string from beginning, if it’s letter, replace with letter from reverse string, else keep special chars and adjust pointer accordingly
3. of course there’s space for improvement, but not necessary

<?php
class Solution {

    /**
     * @param String $S
     * @return String
     */
    function reverseOnlyLetters($S) {
        $x = '';
        $y = '';
        for($i = strlen($S)-1; $i >=0; $i -- ){
            if(ctype_alpha($S[$i])){
                $x .= $S[$i];
            }
        }
        $xi = 0;
        for($i = 0; $i < strlen($S); $i ++){
            if(!ctype_alpha($S[$i])){
                $y .= $S[$i];
            } else {
                $y .= $x[$xi];
                $xi ++;
            }
             
        }
        
        return $y;
    }
}

?>