Tag Archives: Hard

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

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

1032. Stream of Characters

Implement the StreamChecker class as follows:

  • StreamChecker(words): Constructor, init the data structure with the given words.
  • query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

 

Example:

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary.
streamChecker.query('a');          // return false
streamChecker.query('b');          // return false
streamChecker.query('c');          // return false
streamChecker.query('d');          // return true, because 'cd' is in the wordlist
streamChecker.query('e');          // return false
streamChecker.query('f');          // return true, because 'f' is in the wordlist
streamChecker.query('g');          // return false
streamChecker.query('h');          // return false
streamChecker.query('i');          // return false
streamChecker.query('j');          // return false
streamChecker.query('k');          // return false
streamChecker.query('l');          // return true, because 'kl' is in the wordlist

 

Note:

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 2000
  • Words will only consist of lowercase English letters.
  • Queries will only consist of lowercase English letters.
  • The number of queries is at most 40000.

TLE Version (First Draft)

This is the version I submitted during the contest, TLE. (obviously, for a hard question)

My idea was building a tree, well, I just hate writing another class…. so I tried in a hard way during the contest.

class StreamChecker {
    public $max = 0;
    public $hist = "";
    public $d;

    /**
     * @param String[] $words
     */
    function __construct($words) {
        error_reporting(0);
        ini_set('display_errors', 0);
        $this-> d = $words;
        foreach($words as $w){
           $this ->max = max(strlen($w), $this ->max); 
        }
        
    }
  
    /**
     * @param String $letter
     * @return Boolean
     */
    function query($letter) {

        $this ->hist .= $letter;
        foreach($this->d as $f){
            if ($this -> endsWith($this -> hist,$f)) {
                
                return true;
            }
        } 
        if(strlen($this->hist) > $max){
            $this->hist = substr($this->hist, -($this->max));
        }
        
        return false;
    }
    
    function endsWith($haystack, $needle)
    {
        $length = strlen($needle);
        if ($length == 0) {
            return true;
        }
        return (substr($haystack, -$length) === $needle);
    }
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * $obj = StreamChecker($words);
 * $ret_1 = $obj->query($letter);
 */

Another Try

for the query part, if the char is not the last char of any word in the dictionary, return false. The method actually passed all the tests, 2000+ms.

It’s actually a single level trie tree..   in the form of an array.

 

class StreamChecker {
    public $max = 0;
    public $hist = "";
    public $first = [];
    public $d;

    /**
     * @param String[] $words
     */
    function __construct($words) {
        error_reporting(0);
        ini_set('display_errors', 0);
        $this-> d = $words;
        foreach($words as $w){
            $this ->max = max(strlen($w), $this ->max); 
            $this -> first[] = $w[strlen($w)-1];
        }
        
    }
  
    /**
     * @param String $letter
     * @return Boolean
     */
    function query($letter) {
        $this ->hist .= $letter;
        if(!in_array($letter,$this->first)){
            return false;
        }
        foreach($this->d as $f){
            if ($this -> endsWith($this -> hist,$f)) {
                
                return true;
            }
        } 
        if(strlen($this->hist) > $max){
            $this->hist = substr($this->hist, -($this->max));
        }
        
        return false;
    }
    
    function endsWith($haystack, $needle)
    {
        $length = strlen($needle);
        if ($length == 0) {
            return true;
        }
        return (substr($haystack, -$length) === $needle);
    }
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * $obj = StreamChecker($words);
 * $ret_1 = $obj->query($letter);
 */

 

Leetcode

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:

[
  1->4->5,
  1->3->4,
  2->6
]

Output:

 1->1->2->3->4->4->5->6

Thoughts:

This is my accepted but not really efficient solution. (in the last 10% in CPU time and Mem Usage)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode cur = new ListNode(0);
        ListNode result = cur;
        while(!isAllEmpty(lists)){

            int min = Integer.MAX_VALUE;
            int min_index = Integer.MAX_VALUE;
            int i = -1;
            for(ListNode l : lists){
                i ++;
                if (l == null){
                    continue;
                }
                if(l.val < min){
                    min = l.val;
                    min_index = i;
                }
                
            }
           
            cur.next = lists[min_index];
            cur = cur.next;
            lists[min_index] = lists[min_index].next;
        }
        
        return result.next;
    }
    
    
    public boolean isAllEmpty(ListNode[] ln){
        for(ListNode l : ln){
            if(l != null){
                return false;
            }
        }
        return true;
    }
}

 

 

Leetcode

154. Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input:

 [1,3,5]

Output:

 1

Example 2:

Input:

 [2,2,2,0,1]

Output:

 0

Note:

Thoughts:

  • try binary search first, then go through the  ambiguous sections one by one.
My First Draft:
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findMin($nums) {
        $last = count($nums)-1;
        $first = 0;
        $mid = floor(($last + $first) /2);
        $min = null;
        while($nums[$first] > $nums[$mid] xor $nums[$mid] > $nums[$last]){
            if($nums[$first] > $nums[$mid]){
                $last = $mid;
                $mid = floor(($last + $first) /2);
            } else {
                $first = $mid +1;
                $mid = floor(($last + $first) /2);
            }
        }
        if($first == $last){
            return $nums[$last];
        } else {
            for($min = $nums[$first];$first <= $last;$first++){
                if($nums[$first] < $min){
                    $min = $nums[$first];
                }
            }
            
        }
        return $min;
    }

}

 

sheehan‘s pretty solution:
class Solution {
public:
    int findMin(vector<int> &num) {
        int lo = 0;
        int hi = num.size() - 1;
        int mid = 0;
        
        while(lo < hi) {
            mid = lo + (hi - lo) / 2;
            
            if (num[mid] > num[hi]) {
                lo = mid + 1;
            }
            else if (num[mid] < num[hi]) {
                hi = mid;
            }
            else { // when num[mid] and num[hi] are same
                hi--;
            }
        }
        return num[lo];
    }
};

 

Leetcode

996. Number of Squareful Arrays

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1:

Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: [2,2,2]
Output: 1

Note:

1 <= A.length <= 12
0 <= A[i] <= 1e9

Solved this with PHP.

  1. Go through the input and construct array ‘peers’
    1. peers holds an array of pointers pointing to all possible ‘partners’ in the input.
    2. For example, [1 => [8=>ref(8)], 8 => [1=>ref(1), 17=>ref(17)], 17 => [8=>ref(8)]]
  2. Meanwhile, another array stat collect all numbers and its occurrence.
  3. Then peers is recursive. so it’s like a tree, with infinite depth.
  4. Starting from the root of peers, if found any number in ‘stat’, update (-1) stat, and move on to peers’ children
    1. if cannot find any match at some points, break;
    2. since stat is finite, the recursive func will run forever
  5. Calculate the sum.

Works well with even larger input length.

16ms runtime w/ 14.7M RAM

Class Solution {

    /**
     * @param Integer[] $ls
     * @return Integer
     */
    function numSquarefulPerms($ls) {
        
        if(count($ls) <= 1){
            return 0;
        }
        
        $peers = [];
        $stat = [];
        
        for($i = 0; $i < count($ls); $i++){
            // Insert/Update stat
            if(!isset($stat[$ls[$i]])){
                $stat[$ls[$i]] = 1;
            } else {
                $stat[$ls[$i]] ++;
            }
            
            for($j = $i + 1; $j < count($ls); $j++){

                $value_i = $ls[$i];
                $value_j = $ls[$j];
                
                if(!isset($peers[$value_i])){
                    $peers[$value_i] = [];
                }
                if(!isset($peers[$value_j])){
                    $peers[$value_j] = [];
                }
                if($this -> isPerfectSquare($ls[$i] + $ls[$j])){
                    $peers[$value_i][$value_j] = &$peers[$value_j];
                    if($ls[$j] !== $ls[$i]){
                        $peers[$value_j][$value_i] = &$peers[$value_i];
                    }
                }
            }
        }
        // If any number has no partner
        foreach($peers as $p){
            if($p === []){
                return 0;
            }
        }
        return $this->traversal($stat, $peers, count($ls));
    }
    
    // Check if number is perfect square w/ small optimization
    function isPerfectSquare($num){
        $last_digit = $num % 10;
        if($last_digit == 2 ||
            $last_digit == 3 ||
            $last_digit == 7 ||
            $last_digit == 8 
          ) 
            return false;
        
        $sqrt = sqrt($num);
        return $sqrt == floor($sqrt);
    }
    
    function traversal($nums, &$tree, $max){
        $count = 0;
        var_dump($nums);
        if(empty($nums)){
            echo "Add\r\n";
            return 1;
        }
        foreach($tree as $k => $v){
            // Make a copy
            $nums_copy = $nums;
            if(isset($nums_copy[$k])){
                // If exist decrease, if last remove
                if($nums[$k] > 1){
                    $nums_copy[$k] --;
                } else {
                    unset($nums_copy[$k]);
                }
                // move on to children
                $count += $this -> traversal($nums_copy, $v, $max - 1); 
            }     
        }
        return $count;
    }
}
Leetcode

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5


/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    // remove elements from both ends

    
    while ((nums1.length + nums2.length)/2 > 1){
        // If any of the arrays is empty, rm the other one
        if(nums1.length == 0){
            nums2.shift();
            nums2.pop();
        } else if(nums2.length == 0){
            nums1.shift();
            nums1.pop();
        } else {
            if(nums1[0] < nums2[0]){
                nums1.shift();
            } else {
                nums2.shift();
            }
            // if nums1 is empty 
            //   OR nums1's tail is less than nums2's, remove nums2
            if(nums1.length == 0 || 
               nums1[nums1.length -1] < nums2[nums2.length -1]){
                nums2.pop();
            } else {
                nums1.pop();
            }
        }
    }
    // only 1 or 2 elements remain now
    var r = nums1.concat(nums2);
    // send average for two
    if(r.length > 1){
        return (r[0]+r[1])/2;
    } else {
    // or just the last element
        return r[0];
    }
};