# Posts tagged as “medium”

You are given a 0-indexed string word and an integer k.

At every second, you must perform the following operations:

• Remove the first k characters of word.
• Add any k characters to the end of word.

Note that you do not necessarily need to add the same characters that you removed. However, you must perform both operations at every second.

Return the minimum time greater than zero required for word to revert to its initial state.

Example 1:

Input: word = "abacaba", k = 3
Output: 2
Explanation: At the 1st second, we remove characters "aba" from the prefix of word, and add characters "bac" to the end of word. Thus, word becomes equal to "cababac".
At the 2nd second, we remove characters "cab" from the prefix of word, and add "aba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 2 seconds is the minimum time greater than zero required for word to revert to its initial state.


Example 2:

Input: word = "abacaba", k = 4
Output: 1
Explanation: At the 1st second, we remove characters "abac" from the prefix of word, and add characters "caba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 1 second is the minimum time greater than zero required for word to revert to its initial state.


Example 3:

Input: word = "abcbabcd", k = 2
Output: 4
Explanation: At every second, we will remove the first 2 characters of word, and add the same characters to the end of word.
After 4 seconds, word becomes equal to "abcbabcd" and reverts to its initial state.
It can be shown that 4 seconds is the minimum time greater than zero required for word to revert to its initial state.


Constraints:

• 1 <= word.length <= 50
• 1 <= k <= word.length
• word consists only of lowercase English letters.

## Solution: Suffix ==? Prefix

Compare the suffix with prefix.

word = “abacaba”, k = 3
ans = 1, “abacaba” != “abacaba
ans = 2, “abacaba” == “abacaba“, we find it.

Time complexity: O(n * n / k)
Space complexity: O(1)

## C++

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English letters. You are also given two 0-indexed character arrays original and changed, and an integer array cost, where cost[i] represents the cost of changing the character original[i] to the character changed[i].

You start with the string source. In one operation, you can pick a character x from the string and change it to the character y at a cost of z if there exists any index j such that cost[j] == zoriginal[j] == x, and changed[j] == y.

Return the minimum cost to convert the string source to the string target using any number of operations. If it is impossible to convert source to targetreturn -1.

Note that there may exist indices ij such that original[j] == original[i] and changed[j] == changed[i].

Example 1:

Input: source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
Output: 28
Explanation: To convert the string "abcd" to string "acbe":
- Change value at index 1 from 'b' to 'c' at a cost of 5.
- Change value at index 2 from 'c' to 'e' at a cost of 1.
- Change value at index 2 from 'e' to 'b' at a cost of 2.
- Change value at index 3 from 'd' to 'e' at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28.
It can be shown that this is the minimum possible cost.


Example 2:

Input: source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
Output: 12
Explanation: To change the character 'a' to 'b' change the character 'a' to 'c' at a cost of 1, followed by changing the character 'c' to 'b' at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of 'a' to 'b', a total cost of 3 * 4 = 12 is incurred.


Example 3:

Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]
Output: -1
Explanation: It is impossible to convert source to target because the value at index 3 cannot be changed from 'd' to 'e'.


Constraints:

• 1 <= source.length == target.length <= 105
• sourcetarget consist of lowercase English letters.
• 1 <= cost.length == original.length == changed.length <= 2000
• original[i]changed[i] are lowercase English letters.
• 1 <= cost[i] <= 106
• original[i] != changed[i]

## Solution: All pairs shortest path

Compute the shortest path (min cost) for any given letter pairs.

Time complexity: O(26^3 + m + n)
Space complexity: O(26^2)

## C++

You are given two integers, n and k.

An array of distinct positive integers is called a k-avoiding array if there does not exist any pair of distinct elements that sum to k.

Return the minimum possible sum of a k-avoiding array of length n.

Example 1:

Input: n = 5, k = 4
Output: 18
Explanation: Consider the k-avoiding array [1,2,4,5,6], which has a sum of 18.
It can be proven that there is no k-avoiding array with a sum less than 18.


Example 2:

Input: n = 2, k = 6
Output: 3
Explanation: We can construct the array [1,2], which has a sum of 3.
It can be proven that there is no k-avoiding array with a sum less than 3.


Constraints:

• 1 <= n, k <= 50

## Solution 1: Greedy + HashTable

Always choose the smallest possible number starting from 1.

Add all chosen numbers into a hashtable. For a new candidate i, check whether k – i is already in the hashtable.

Time complexity: O(n)
Space complexity: O(n)

## C++

You are given two 0-indexed strings str1 and str2.

In an operation, you select a set of indices in str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is 'a' becomes 'b''b' becomes 'c', and so on, and 'z' becomes 'a'.

Return true if it is possible to make str2 a subsequence of str1 by performing the operation at most onceand false otherwise.

Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.

Example 1:

Input: str1 = "abc", str2 = "ad"
Output: true
Explanation: Select index 2 in str1.
Increment str1[2] to become 'd'.
Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.

Example 2:

Input: str1 = "zc", str2 = "ad"
Output: true
Explanation: Select indices 0 and 1 in str1.
Increment str1[0] to become 'a'.
Increment str1[1] to become 'd'.
Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.

Example 3:

Input: str1 = "ab", str2 = "d"
Output: false
Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once.
Therefore, false is returned.

Constraints:

• 1 <= str1.length <= 105
• 1 <= str2.length <= 105
• str1 and str2 consist of only lowercase English letters.

## Solution: Two pointers

s1[i] and s2[j] can match if
s1[i] == s2[j] or inc(s1[i]) == s2[j]

If matched: ++i; ++j else ++i.

Time complexity: O(n)
Space complexity: O(1)

Iterator version

## C++

You are given two 0-indexed integer arrays nums1 and nums2 of length n.

Let’s define another 0-indexed integer array, nums3, of length n. For each index i in the range [0, n - 1], you can assign either nums1[i] or nums2[i] to nums3[i].

Your task is to maximize the length of the longest non-decreasing subarray in nums3 by choosing its values optimally.

Return an integer representing the length of the longest non-decreasing subarray in nums3.

Note: subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums1 = [2,3,1], nums2 = [1,2,1]
Output: 2
Explanation: One way to construct nums3 is:
nums3 = [nums1[0], nums2[1], nums2[2]] => [2,2,1].
The subarray starting from index 0 and ending at index 1, [2,2], forms a non-decreasing subarray of length 2.
We can show that 2 is the maximum achievable length.

Example 2:

Input: nums1 = [1,3,2,1], nums2 = [2,2,3,4]
Output: 4
Explanation: One way to construct nums3 is:
nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] => [1,2,3,4].
The entire array forms a non-decreasing subarray of length 4, making it the maximum achievable length.


Example 3:

Input: nums1 = [1,1], nums2 = [2,2]
Output: 2
Explanation: One way to construct nums3 is:
nums3 = [nums1[0], nums1[1]] => [1,1].
The entire array forms a non-decreasing subarray of length 2, making it the maximum achievable length.


Constraints:

• 1 <= nums1.length == nums2.length == n <= 105
• 1 <= nums1[i], nums2[i] <= 109

## Solution: DP

Let dp1(i), dp2(i) denote the length of the Longest Non-decreasing Subarray ends with nums1[i] and nums2[i] respectively.

init: dp1(0) = dp2(0) = 1

dp1(i) = max(dp1(i – 1) + 1 if nums1[i] >= nums1[i – 1] else 1, dp2(i – 1) + 1 if nums1[i] >= nums2[i – 1] else 1)
dp2(i) = max(dp1(i – 1) + 1 if nums2[i] >= nums1[i – 1] else 1, dp2(i – 1) + 1 if nums2[i] >= nums2[i – 1] else 1)

ans = max(dp1, dp2)

Time complexity: O(n)
Space complexity: O(n) -> O(1)