• Input 0,1,2 (respectively stands for '(', ')', "()" ) to a linked list, then find the longest subsequence of 2.

``````public int longestValidParentheses(String s) {
int n = s.length();
if(s.length() < 2) return 0;
int left = 0;
for(char c : s.toCharArray())
{
if(c == '(')
{
left++;
}
else
{
if(left > 0)
{
list.removeLastOccurrence(0);
left--;
}
else
{
}
}
}
int two = 0;
int max = 0;
boolean flag = true;
for(int num : list)
{
if(num == 2)
{
two++;
if(!flag) flag = true;
}
else
{
if(flag)
{
max = Math.max(two, max);
two = 0;
flag = false;
}
}
}
max = Math.max(two, max);
return 2 * max;
}``````

• In the second part, I tried:

int maxCount = 0;
int two = 0;
for(int i=0; i<countMap.size(); i++) {
if(countMap.get(i)==2)
{
while(i<countMap.size() && countMap.get(i)==2) {
two++;
i++;
}
maxCount = Math.max(maxCount, two*2);
two = 0;
}
}
return maxCount;

It still seems to me that the run time is O(n) but, mine is much slower than yours. Do you have any idea why?
mine = 150 ms, yours = 6 ms. Thanks a lot.

• I guess I found the solution. for(int num : list) is much faster than for(int i=0; i<countMap.size(); i++).

• You're right. Visiting elements of a LinkedList by index is very time-consuming.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.