The Easiest LeetCode Contest in 2021

This LeetCode contest is sponsored by Amazon Pay. Check out [Weekly Contest 272](https://leetcode.com/contest/weekly-contest-272) for the questions. ## Q1 - 2108. Find First Palindromic String in the Array Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "". A string is palindromic if it reads the same forward and backward. ### Example 1: Input: words = ["abc","car","ada","racecar","cool"] Output: "ada" Explanation: The first string that is palindromic is "ada". Note that "racecar" is also palindromic, but it is not the first. ### Example 2: Input: words = ["notapalindrome","racecar"] Output: "racecar" Explanation: The first and only string that is palindromic is "racecar". ### Example 3: Input: words = ["def","ghi"] Output: "" Explanation: There are no palindromic strings, so the empty string is returned. ## Solution There are several ways to check if $s$ is a palindrome. ### Long and Efficient ```cpp bool isPalindrome(const string& s) { for (int i = 0; i < s.size() / 2; i++) { if (s[i] != s[s.size() - i - 1]) return false; } return true; } ``` ### Shorter but not efficient ```cpp bool isPalindrome(const string& s) { string t = s; reverse(t.begin(), t.end()); return s == t; } ``` ### Shortest but not efficient ```cpp bool isPalindrome(const string& s) { return s == string(s.rbegin(), s.rend()); } ``` ### Shortest but efficient ```cpp bool isPalindrome(const string &s) { return equal(s.begin(), s.begin() + s.size() / 2, s.rbegin()); } ``` We just need to iterate each string and check if the target $s$ is a palindrome, return the string if so. ``` class Solution { public: bool isPalindrome(const string& s) { return equal(s.begin(), s.begin() + s.size() / 2, s.rbegin()); } string firstPalindrome(vector& words) { for (auto s : words) { if (isPalindrome(s)) { return s; } } return ""; } }; ``` ## Q2 - 2109. Adding Spaces to a String You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index. For example, given s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee". Return the modified string after the spaces have been added. ### Example 1: Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15] Output: "Leetcode Helps Me Learn" Explanation: The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn". We then place spaces before those characters. ### Example 2: Input: s = "icodeinpython", spaces = [1,5,7,9] Output: "i code in py thon" Explanation: The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython". We then place spaces before those characters. ### Example 3: Input: s = "spacing", spaces = [0,1,2,3,4,5,6] Output: " s p a c i n g" Explanation: We are also able to place spaces before the first character of the string. ## Solution Two-pointer. i-th pointer is for string $s$ and j-th pointer is for spaces vector. Iterate string $s$, if $i$ matches $spaces[j]$, then add a space and increase $j$ by 1. ``` class Solution { public: string addSpaces(string s, vector& spaces) { string ans; int j = 0, m = spaces.size(); for (int i = 0; i < s.size(); i++) { if (j < m && i == spaces[j]) ans += " ", j++; ans += s[i]; } return ans; } }; ``` ## Q3 - 2110. Number of Smooth Descent Periods of a Stock You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the ith day. A smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule. Return the number of smooth descent periods. ### Example 1: Input: prices = [3,2,1,4] Output: 7 Explanation: There are 7 smooth descent periods: [3], [2], [1], [4], [3,2], [2,1], and [3,2,1] Note that a period with one day is a smooth descent period by the definition. ### Example 2: Input: prices = [8,6,7,7] Output: 4 Explanation: There are 4 smooth descent periods: [8], [6], [7], and [7] Note that [8,6] is not a smooth descent period as 8 - 6 ≠ 1. ### Example 3: Input: prices = [1] Output: 1 Explanation: There is 1 smooth descent period: [1] ## Solution The first observation is each number is a smooth descent period. The final answer is at least $ n $ which is the size of the given vector. Therefore, the initial value for $dp[i]$ is $1$. The second observation is that we can add $dp[i - 1]$ to $dp[i]$ if $prices[i - 1] - prices[i] = 1$ starting from $i = 1$. ``` class Solution { public: long long getDescentPeriods(vector& prices) { int n = prices.size(); long long ans = 0; vector dp(n, 1); for (int i = 0; i < n; i++) { if (i > 0 && prices[i - 1] - prices[i] == 1) { dp[i] += dp[i - 1]; } ans += dp[i]; } return ans; } }; ``` ## Q4 - 2111. Minimum Operations to Make the Array K-Increasing You are given a 0-indexed array arr consisting of n positive integers, and a positive integer k. The array arr is called K-increasing if arr[i-k] <= arr[i] holds for every index i, where k <= i <= n-1. For example, arr = [4, 1, 5, 2, 6, 2] is K-increasing for k = 2 because: arr[0] <= arr[2] (4 <= 5) arr[1] <= arr[3] (1 <= 2) arr[2] <= arr[4] (5 <= 6) arr[3] <= arr[5] (2 <= 2) However, the same arr is not K-increasing for k = 1 (because arr[0] > arr[1]) or k = 3 (because arr[0] > arr[3]). In one operation, you can choose an index i and change arr[i] into any positive integer. Return the minimum number of operations required to make the array K-increasing for the given k. ### Example 1: Input: arr = [5,4,3,2,1], k = 1 Output: 4 Explanation: For k = 1, the resultant array has to be non-decreasing. Some of the K-increasing arrays that can be formed are [5,6,7,8,9], [1,1,1,1,1], [2,2,3,4,4]. All of them require 4 operations. It is suboptimal to change the array to, for example, [6,7,8,9,10] because it would take 5 operations. It can be shown that we cannot make the array K-increasing in less than 4 operations. ### Example 2: Input: arr = [4,1,5,2,6,2], k = 2 Output: 0 Explanation: This is the same example as the one in the problem description. Here, for every index i where 2 <= i <= 5, arr[i-2] <= arr[i]. Since the given array is already K-increasing, we do not need to perform any operations. ### Example 3: Input: arr = [4,1,5,2,6,2], k = 3 Output: 2 Explanation: Indices 3 and 5 are the only ones not satisfying arr[i-3] <= arr[i] for 3 <= i <= 5. One of the ways we can make the array K-increasing is by changing arr[3] to 4 and arr[5] to 5. The array will now be [4,1,5,4,6,5]. Note that there can be other ways to make the array K-increasing, but none of them require less than 2 operations. ## Solution We can break input vector into $k$ groups $a_i, a_{i + k}, a_{i + 2 * k}, ...$ for each $ i < k$. Calculate the LIS (Longest Increasing Subsequence) on each group and compare the length with the target size. We need to perform $a.size() - lengthOfLIS(a)$ operations to make it K-increasing. ``` class Solution { public: int lengthOfLIS(vector& nums) { int n = (int) nums.size(); vector lis; for(int i = 0; i < n; i++) { auto it = upper_bound(lis.begin(), lis.end(), nums[i]); if(it == lis.end()) lis.push_back(nums[i]); else *it = nums[i]; } return (int) lis.size(); } int kIncreasing(vector& arr, int k) { int ans = 0, n = arr.size(); for (int i = 0; i < k; i++) { vector a; for (int j = i; j < n; j += k) { a.push_back(arr[j]); } ans += a.size() - lengthOfLIS(a); } return ans; } }; ```