Posts tagged as “longest”

花花酱 LeetCode 1493. Longest Subarray of 1’s After Deleting One Element

By zxi on June 27, 2020

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1’s in the resulting array.

Return 0 if there is no such subarray.

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Example 4:

Input: nums = [1,1,0,0,1,1,1,0,1]
Output: 4

Example 5:

Input: nums = [0,0,0]
Output: 0

Constraints:

1 <= nums.length <= 10^5
nums[i] is either 0 or 1.

Solution 1: DP

Preprocess:
l[i] := longest 1s from left side ends with nums[i], l[i] = nums[i] + nums[i] * l[i – 1]
r[i] := longest 1s from right side ends with nums[i], r[i] = nums[i] + nums[i] * r[i + 1]

Use each node as a bridge (ignored), the total number of consecutive 1s = l[i – 1] + r[i + 1].

ans = max{l[i-1] + r[i +1]}
Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

vector<int> l(n);

vector<int> r(n);

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

l[i] = (i > 0 ? l[i - 1] * nums[i] : 0) + nums[i];

for (int i = n - 1; i >= 0; --i)

r[i] = (i < n - 1 ? r[i + 1] * nums[i] : 0) + nums[i];

int ans = 0;

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

ans = max(ans, (i > 0 ? l[i - 1] : 0) +

(i < n - 1 ? r[i + 1] : 0));

return ans;

}

};

Solution 2: DP

dp[i][0] := longest subarray ends with nums[i] has no ones.
dp[i][0] := longest subarray ends with nums[i] has 1 one.
if nums[i] == 1:
dp[i][0] = dp[i – 1][0] + 1
dp[i][1] = dp[i – 1][1] + 1
if nums[i] == 0:
dp[i][0] = 0
dp[i][1] = dp[i – 1][0] + 1
Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

// dp[i][0] := longest subarray ends with nums[i-1] has no zeros.

// dp[i][0] := longest subarray ends with nums[i-1] has 1 zero.

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

int ans = 0;

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

if (nums[i - 1] == 1) {

dp[i][0] = dp[i - 1][0] + 1;

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

} else {

dp[i][0] = 0;

dp[i][1] = dp[i - 1][0] + 1;

}

ans = max({ans, dp[i][0] - 1, dp[i][1] - 1});

}

return ans;

}

};

Solution 3: Sliding Window

Maintain a sliding window l ~ r s.t sum(num[l~r]) >= r – l. There can be at most one 0 in the window.
ans = max{r – l} for all valid windows.

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

C++

// Author: Huahua

class Solution {

public:

int longestSubarray(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

int sum = 0; // sum of nums[l~r].

for (int l = 0, r = 0; r < n; ++r) {

sum += nums[r];

// Maintain sum >= r - l, at most 1 zero.

while (l < r && sum < r - l)

sum -= nums[l++];

ans = max(ans, r - l);

}

return ans;

}

};

花花酱 LeetCode 5. Longest Palindromic Substring

By zxi on September 12, 2018

Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Solution: DP

Try all possible i and find the longest palindromic string whose center is i (odd case) and i / i + 1 (even case).

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua, 16 ms, 8.7 MB

class Solution {

public:

string longestPalindrome(string s) {

const int n = s.length();

auto getLen = [&](int l, int r) {

while (l >= 0 && r < n

&& s[l] == s[r]) {

--l;

++r;

}

return r - l - 1;

};

int len = 0;

int start = 0;

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

int cur = max(getLen(i, i),

getLen(i, i + 1));

if (cur > len) {

len = cur;

start = i - (len - 1) / 2;

}

return s.substr(start, len);

}

};

Java

// Author: Huahua, 6 ms， 36.5 MB

class Solution {

public String longestPalindrome(String s) {

int len = 0;

int start = 0;

for (int i = 0; i < s.length(); ++i) {

int cur = Math.max(getLen(s, i, i),

getLen(s, i, i + 1));

if (cur > len) {

len = cur;

start = i - (cur - 1) / 2;

}

return s.substring(start, start + len);

}

private int getLen(String s, int l, int r) {

while (l >= 0 && r < s.length()

&& s.charAt(l) == s.charAt(r)) {

--l;

++r;

}

return r - l - 1;

}

Python3

# Author: Huahua, 812 ms, 12.7MB

class Solution:

def longestPalindrome(self, s: str) -> str:

n = len(s)

def getLen(l, r):

while l >= 0 and r < n and s[l] == s[r]:

l -= 1

r += 1

return r - l - 1

start = 0

length = 0

for i in range(n):

cur = max(getLen(i, i),

getLen(i, i + 1))

if cur <= length: continue

length = cur

start = i - (cur - 1) // 2

return s[start : start + length]

花花酱 LeetCode 845. Longest Mountain in Array

By zxi on June 3, 2018

Problem

题目大意：找出最长的山形子数组。

https://leetcode.com/problems/longest-mountain-in-array/description/

Let’s call any (contiguous) subarray B (of A) a mountain if the following properties hold:

B.length >= 3
There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain.

Return 0 if there is no mountain.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

Note:

0 <= A.length <= 10000
0 <= A[i] <= 10000

Solution: DP

Three passes

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

int longestMountain(vector<int>& A) {

vector<int> inc(A.size());

vector<int> dec(A.size());

for (int i = 1; i < A.size(); ++i)

if (A[i] > A[i - 1]) inc[i] = inc[i - 1] + 1;

for (int i = A.size() - 2; i > 0; --i)

if (A[i] > A[i + 1]) dec[i] = dec[i + 1] + 1;

int ans = 0;

for (int i = 0; i < A.size(); ++i)

if (inc[i] && dec[i])

ans = max(ans, inc[i] + dec[i] + 1);

return ans >= 3 ? ans : 0;

}

};

One pass

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

int longestMountain(vector<int>& A) {

int inc = 0;

int dec = 0;

int ans = 0;

for (int i = 1; i < A.size(); ++i) {

if (dec && A[i] > A[i - 1] || A[i] == A[i - 1])

dec = inc = 0;

inc += A[i] > A[i - 1];

dec += A[i] < A[i - 1];

if (inc && dec)

ans = max(ans, inc + dec + 1);

}

return ans >= 3 ? ans : 0;

}

};

花花酱 LeetCode 594. Longest Harmonious Subsequence

By zxi on March 20, 2018

Problem

https://leetcode.com/problems/longest-harmonious-subsequence/description/

题目大意：找一个最长子序列，要求子序列中最大值和最小值的差是1。

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

Solution1: HashTable

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

C++

// Author: Huahua

// Running time: 127 ms

class Solution {

public:

int findLHS(vector<int>& nums) {

unordered_map<int, int> counts;

int ans = 0;

for (int num : nums) {

++counts[num];

int l = counts[num - 1];

int h = counts[num + 1];

if (l || h)

ans = max(ans, counts[num] + max(l, h));

}

return ans;

}

};

// Running time: 109 ms

class Solution {

public:

int findLHS(vector<int>& nums) {

unordered_map<int, int> counts;

int ans = 0;

for (int num : nums) {

const int c = ++counts[num];

auto it1 = counts.find(num - 1);

auto it2 = counts.find(num + 1);

if (it1 != counts.end())

ans = max(ans, c + it1->second);

if (it2 != counts.end())

ans = max(ans, c + it2->second);

}

return ans;

}

};

// Author: Huahua

// Running time: 102 ms

class Solution {

public:

int findLHS(vector<int>& nums) {

unordered_map<int, int> counts;

int ans = 0;

for (int num : nums)

++counts[num];

for (const auto& p : counts) {

auto it1 = counts.find(p.first - 1);

auto it2 = counts.find(p.first + 1);

if (it1 != counts.end())

ans = max(ans, p.second + it1->second);

if (it2 != counts.end())

ans = max(ans, p.second + it2->second);

}

return ans;

}

};

花花酱 LeetCode 128. Longest Consecutive Sequence

By zxi on October 2, 2017

Problem:

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Idea:

Hashtable / Hashset

Time complexity: O(n)

Space complexity: O(n)

Solution 1: C++ / online

class Solution {

public:

int longestConsecutive(vector<int>& nums) {

unordered_map<int, int> h;

int ans = 0;

for (int num : nums) {

if (h.count(num)) continue;

auto it_l = h.find(num - 1);

auto it_r = h.find(num + 1);

int l = it_l != h.end() ? it_l->second : 0;

int r = it_r != h.end() ? it_r->second : 0;

int t = l + r + 1;

h[num] = h[num - l] = h[num + r] = t;

ans = max(ans, t);

}

return ans;

}

};

Solution 2: C++ / offline

class Solution {

public:

int longestConsecutive(vector<int>& nums) {

unordered_set<int> h(nums.begin(), nums.end());

int ans = 0;

for (int num : nums)

if (!h.count(num - 1)) {

int l = 0;

while (h.count(num++)) ++l;

ans = max(ans, l);

}

return ans;

}

};