Huahua’s Tech Road

花花酱 LeetCode 1177. Can Make Palindrome from Substring

By zxi on September 1, 2019

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], ..., s[right], and then choose up to k of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = "aaa", and k = 2, we can only replace two of the letters. (Also, note that the initial string s is never modified by any query.)

Example :

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0] : substring = "d", is palidrome.
queries[1] : substring = "bc", is not palidrome.
queries[2] : substring = "abcd", is not palidrome after replacing only 1 character.
queries[3] : substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4] : substring = "abcda", could be changed to "abcba" which is palidrome.

Constraints:

1 <= s.length, queries.length <= 10^5
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s only contains lowercase English letters.

Solution: Prefix frequency

Compute the prefix frequency of each characters, then we can efficiently compute the frequency of each characters in the substring in O(1) time. Count the number odd frequency characters o, we can convert it to a palindrome if o / 2 <= k.

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

C++

// Author: Huahua

class Solution {

public:

vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {

vector<bool> ans;

int n = s.length();

vector<vector<int>> f(n + 1, vector<int>(26));

for (int i = 0; i < n; ++i) {

++f[i][s[i] - 'a'];

f[i + 1] = f[i];

}

for (const auto& q : queries) {

int l = q[0];

int r = q[1];

int k = q[2];

int o = 0;

for (int i = 0; i < 26; ++i) {

int c = f[r][i] - (l == 0 ? 0 : f[l - 1][i]);

o += c % 2;

}

ans.push_back(o / 2 <= k);

}

return ans;

}

};

花花酱 LeetCode 1176. Diet Plan Performance

By zxi on August 31, 2019

A dieter consumes calories[i] calories on the i-th day. For every consecutive sequence of k days, they look at T, the total calories consumed during that sequence of k days:

If T < lower, they performed poorly on their diet and lose 1 point;
If T > upper, they performed well on their diet and gain 1 point;
Otherwise, they performed normally and there is no change in points.

Return the total number of points the dieter has after all calories.length days.

Note that: The total points could be negative.

Example 1:

Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0
Explaination: calories[0], calories[1] < lower and calories[3], calories[4] > upper, total points = 0.

Example 2:

Input: calories = [3,2], k = 2, lower = 0, upper = 1
Output: 1
Explaination: calories[0] + calories[1] > upper, total points = 1.

Example 3:

Input: calories = [6,5,0,0], k = 2, lower = 1, upper = 5
Output: 0
Explaination: calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, total points = 0.

Constraints:

1 <= k <= calories.length <= 10^5
0 <= calories[i] <= 20000
0 <= lower <= upper

Solution: Sliding Window

Maintain the sum of a sliding window length of k.

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

C++

// Author: Huahua

class Solution {

public:

int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {

int ans = 0;

int t = accumulate(begin(calories), begin(calories) + k - 1, 0);

for (int i = k - 1; i < calories.size(); ++i) {

if (i >= k) t -= calories[i - k];

t += calories[i];

if (t > upper) ++ans;

if (t < lower) --ans;

}

return ans;

}

};

花花酱 LeetCode 1175. Prime Arrangements

By zxi on August 31, 2019

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2:

Input: n = 100
Output: 682289015

Constraints:

1 <= n <= 100

Solution: Permutation

Count the number of primes in range [1, n], assuming there are p primes and n – p non-primes, we can permute each group separately.
ans = p! * (n – p)!

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

C++

// Author: Huahua

class Solution {

public:

int numPrimeArrangements(int n) {

const int kMod = 1e9 + 7;

int p = 0;

for (int i = 1; i <= n; ++i)

p += isPrime(i);

long ans = 1;

for (int i = 1; i <= p; ++i)

ans = (ans * i) % kMod;

for (int i = 1; i <= n - p; ++i)

ans = (ans * i) % kMod;

return ans;

}

private:

bool isPrime(int x) {

if (x < 2) return false;

if (x == 2) return true;

for (int i = 2; i <= sqrt(x); ++i)

if (x % i == 0) return false;

return true;

}

};

花花酱 LeetCode 1143. Longest Common Subsequence

By zxi on August 29, 2019

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

1 <= text1.length <= 1000
1 <= text2.length <= 1000
The input strings consist of lowercase English characters only.

Solution: DP

Use dp[i][j] to represent the length of longest common sub-sequence of text1[0:i] and text2[0:j]
dp[i][j] = dp[i – 1][j – 1] + 1 if text1[i – 1] == text2[j – 1] else max(dp[i][j – 1], dp[i – 1][j])

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

C++

// Author: Huahua, 16ms 14.9 MB

class Solution {

public:

int longestCommonSubsequence(string text1, string text2) {

int m = text1.length();

int n = text2.length();

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

if (text1[i] == text2[j])

dp[i + 1][j + 1] = dp[i][j] + 1;

else

dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);

return dp[m][n];

}

};

C++/V2

// Author: Huahua, 8ms, 8.8MB

class Solution {

public:

int longestCommonSubsequence(string text1, string text2) {

int m = text1.length();

int n = text2.length();

vector<int> dp(n + 1);

for (int i = 0; i < m; ++i) {

int prev = 0; // dp[i][j]

for (int j = 0; j < n; ++j) {

int curr = dp[j + 1]; // dp[i][j + 1]

if (text1[i] == text2[j])

// dp[i + 1][j + 1] = dp[i][j] + 1

dp[j + 1] = prev + 1;

else

// dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

dp[j + 1] = max(curr, dp[j]);

prev = curr;

}

return dp[n]; // dp[m][n]

}

};

C++/V3

// Author: Huahua

class Solution {

public:

int longestCommonSubsequence(string text1, string text2) {

int m = text1.length();

int n = text2.length();

vector<int> dp1(n + 1);

vector<int> dp2(n + 1);

for (int i = 0; i < m; ++i) {

for (int j = 0; j < n; ++j)

if (text1[i] == text2[j])

dp2[j + 1] = dp1[j] + 1;

else

dp2[j + 1] = max(dp1[j + 1], dp2[j]);

swap(dp1, dp2);

}

return dp1[n];

}

};

花花酱 LeetCode 1171. Remove Zero Sum Consecutive Nodes from Linked List

By zxi on August 24, 2019

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:

The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.

Solution: HashTable

Similar to target sum = 0, use a hashtable to store the first ListNode* that has a given prefix sum. Whenever the same prefix sum occurs, skip all the elements between the first occurrence and current one, e.g. first_sum_x.next = curr_sum_x.next

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

C++

// Author: Huahua

class Solution {

public:

ListNode* removeZeroSumSublists(ListNode* head) {

bool done = false;

function<ListNode*(ListNode*)> helper = [&](ListNode* head) {

ListNode dummy(0);

dummy.next = head;

ListNode* prev = &dummy;

ListNode* curr = prev->next;

unordered_map<int, ListNode*> m{{0, prev}};

int s = 0;

done = true;

while (curr) {

s += curr->val;

if (m.count(s)) {

m[s]->next = curr->next;

done = false;

} else {

m[s] = curr;

}

prev = curr;

curr = curr->next;

}

return dummy.next;

};

while (!done) head = helper(head);

return head;

}

};

Python3

# Author: Huahua

class Solution:

def removeZeroSumSublists(self, head: ListNode) -> ListNode:

def helper(head: ListNode):

dummy = ListNode(0)

dummy.next = head

prev, curr = dummy, dummy.next

s = 0

m = {s: prev}

done = True

while curr:

s += curr.val

if s in m:

m[s].next = curr.next

done = False

else:

m[s] = curr

prev, curr = curr, curr.next

return dummy.next, done

while True:

head, done = helper(head)

if done: return head

Huahua's Tech Road

花花酱 LeetCode 1177. Can Make Palindrome from Substring

Solution: Prefix frequency

C++

花花酱 LeetCode 1176. Diet Plan Performance

Solution: Sliding Window

C++

花花酱 LeetCode 1175. Prime Arrangements

Solution: Permutation

C++

花花酱 LeetCode 1143. Longest Common Subsequence

C++

C++/V2

C++/V3

花花酱 LeetCode 1171. Remove Zero Sum Consecutive Nodes from Linked List

Solution: HashTable

C++

Python3