Tag Archives: Leetcode

Leetcode

640. Solve the Equation

Solve a given equation and return the value of x in the form of string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable x and its coefficient.

If there is no solution for the equation, return “No solution”.

If there are infinite solutions for the equation, return “Infinite solutions”.

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"



class Solution {
    public String solveEquation(String equation) {
        String[] explodes = equation.split("=");
        
        int coeffX = 0;
        int number = 0;
        int cur  = 0;
        int digit = 0;
        
        boolean left = false;
        
        for (String s : explodes){
            left = !left;
            boolean positive = true;
            
            for (int i = 0; i < s.length(); i ++){
                char c = s.charAt(i);
                
                if (c == '+' || c == '-'){
                    // Push previous integer to number
                    number -= cur*(positive? 1 : -1)*(left? 1 : -1);
                    cur = 0; digit = 0;
                    positive = c == '+';
                    
                } else if(c =='x') {
                    // Push previous coeff of x to coeffX
                    if (digit == 0){
                        // If no coeff, coeff = 1
                        cur = 1;
                    }
                    coeffX += cur*(positive? 1 : -1)*(left? 1 : -1);
                    cur = 0; digit = 0;
                } else {
                    // It's a number.
                    cur = 10 * cur +  Integer.valueOf(s.charAt(i)-'0');
                    digit ++;
                }
            }
            
            // If last in group is a number, redundant
            if (digit > 0){
                number += cur*( ! positive? 1 : -1)*(left? 1 : -1);
                cur = 0; digit = 0;
            }
        }
        
        if (coeffX == 0 && number == 0){
            return "Infinite solutions";
        } else if (coeffX == 0){
            return "No solution";
        }
        return "x="+String.valueOf(number/coeffX);
    }
}

 

Leetcode

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

 

Leetcode

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
Leetcode

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

Leetcode

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;
        result.add(x);
        result.add(cheeseSlices-x);
        
        return result;
    }
}

 

Leetcode

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

 

Leetcode

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

 

Leetcode

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"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]

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)){
                    rr.add(products[j]);
                }
            }

            r.add (rr);
        }
        return r;
    }
}

 

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