JS, TS dynamic programming solution. Explained.
Dynamic programming with tabulation. \n\n1. Algorithm\n2. JavaScript solution\n3. TypeScript solution\n\n Intro \n\nLet\'s say we have a string: \' ( ) ( ( ) ( 
<h2>Dynamic programming with tabulation.</h2>\n\n1. <a href="#algo">Algorithm</a>\n2. <a href="#javascript-solution">JavaScript solution</a>\n3. <a href="#typescript-solution">TypeScript solution</a>\n\n<h3>Intro</h3>\n\nLet\'s say we have a string: \' ( ) ( ( ) ( ) ) \'.\nThe resulting array we got using this approach looks like this (**only the last row** actually):\n\n<table>\n\t<tr>\n\t\t<td><b>i</b></td>\n\t\t<td>0</td>\n\t\t<td>1</td>\n\t\t<td>2</td>\n\t\t<td>3</td>\n\t\t<td>4</td>\n\t\t<td>5</td>\n\t\t<td>6</td>\n\t\t<td>7</td>\n\t\t<td> - an index</td>\n\t</tr>\n\t<tr>\n\t\t<td><b>s</b></td>\n\t\t<td>(</td>\n\t\t<td>)</td>\n\t\t<td>(</td>\n\t\t<td>(</td>\n\t\t<td>)</td>\n\t\t<td>(</td>\n\t\t<td>)</td>\n\t\t<td>)</td>\n\t\t<td> - a given string</td>\n\t</tr>\n\t<tr>\n\t\t<td><b>dp</b></td>\n\t\t<td>0</td>\n\t\t<td>2</td>\n\t\t<td>0</td>\n\t\t<td>0</td>\n\t\t<td>2</td>\n\t\t<td>0</td>\n\t\t<td>4</td>\n\t\t<td>8</td>\n\t\t<td> - a dynamic programming tabulation</td>\n\t</tr>\n</table>\n\nThe numbers in **dp** indicate the length of the valid parentheses substring ending at the corresponding index.\nThe largest number of the **dp** will indicate *the length of the longest parentheses substring*.\n\n<h3 id="algo">Algorithm</h3>\n\n1. Initialise the **dp** array with zeros. The length of the array equals to the length of the string (e.g. length = 8).\n\n<table>\n\t<tr>\n\t\t<td><b>dp</b></td>\n\t\t<td>0</td>\n\t\t<td>0</td>\n\t\t<td>0</td>\n\t\t<td>0</td>\n\t\t<td>0</td>\n\t\t<td>0</td>\n\t\t<td>0</td>\n\t\t<td>0</td>\n\t</tr>\n</table>\n\n2. We will be checking two adjacent charachters of  the given string (**s[ i - 1 ]** and **s[ i ]**, for i = 1, 2, ... , length-1).\n<table>\n\t<tr>\n\t\t<td><b>i</b></td>\n\t\t<td><b>[ 0 ]</b></td>\n\t\t<td><b>[ 1 ]</b></td>\n\t\t<td>2</td>\n\t\t<td>...</td>\n\t\t<td rowspan="2"> => </td>\n\t\t<td><b>i</b></td>\n\t\t<td>0</td>\n\t\t<td><b>[ 1 ]</b></td>\n\t\t<td><b>[ 2 ]</b></td>\n\t\t<td>...</td>\n\t\t<td rowspan="2"> => </td>\n\t\t<td><b>i</b></td>\n\t\t<td>...</td>\n\t\t<td><b>[ 2 ]</b></td>\n\t\t<td><b>[ 3 ]</b></td>\n\t\t<td>...</td>\n\t</tr>\n\t<tr>\n\t\t<td><b>s</b></td>\n\t\t<td><b>[ ( ]</b></td>\n\t\t<td><b>[ ) ]</b></td>\n\t\t<td>(</td>\n\t\t<td>...</td>\n\t\t<td><b>s</b></td>\n\t\t<td>(</td>\n\t\t<td><b>[ ) ]</b></td>\n\t\t<td><b>[ ( ]</b></td>\n\t\t<td>...</td>\n\t\t<td><b>s</b></td>\n\t\t<td>...</td>\n\t\t<td><b>[ ( ]</b></td>\n\t\t<td><b>[ ( ]</b></td>\n\t\t<td>...</td>\n\t</tr>\n</table>\n\n* We will take into consideration only **two conditions**:\n\t*a.*  s[ i - 1 ] == \' **(** \' && s[ i ] == \' **)** \';\n\t*b.* s[ i - 1 ] == \' **)** \' && s[ i ] == \' **)** \'.\n\n3. *Condition a.* means that we have found a valid substring \' **( )** \' of parentheses of length 2. So we can put the length = 2 of that substring in the **dp** at index i: **dp[ i ] = 2**\n\n<table>\n\t<tr>\n\t\t<td><b>i</b></td>\n\t\t<td><b>0</b></td>\n\t\t<td><b>1</b></td>\n\t</tr>\n\t<tr>\n\t\t<td><b>s</b></td>\n\t\t<td><b>(</b></td>\n\t\t<td><b>)</b></td>\n\t</tr>\n\t<tr>\n\t\t<td><b>dp</b></td>\n\t\t<td>0</td>\n\t\t<td>2</td>\n\t</tr>\n</table>\n\n* But it could be a subsequent valid substring (e.g. **i = 5 to 6** - this valid substing is a part of the bigger valid substring **i = 3 to 6**). So we also have to check the value in **dp[ i - 2 ]**, and the resulting equation for *condition a.* will be **dp[ i ] = 2 + dp[ i - 2]**.\n\nFor **i = 4** and next **i = 6** (i = 5 does not fall under *condition a.*)\n<table>\n\t<tr>\n\t\t<td><b>i</b></td>\n\t\t<td>...</td>\n\t\t<td>2</td>\n\t\t<td><b>3</b></td>\n\t\t<td><b>4</b></td>\n\t\t<td rowspan="3"> => </td>\n\t\t<td><b>i</b></td>\n\t\t<td>...</td>\n\t\t<td>4</td>\n\t\t<td><b>5</b></td>\n\t\t<td><b>6</b></td>\n\t</tr>\n\t<tr>\n\t\t<td><b>s</b></td>\n\t\t<td>...</td>\n\t\t<td>(</td>\n\t\t<td><b>(</b></td>\n\t\t<td><b>)</b></td>\n\t\t<td><b>s</b></td>\n\t\t<td>...</td>\n\t\t<td>)</td>\n\t\t<td><b>(</b></td>\n\t\t<td><b>)</b></td>\n\t</tr>\n\t<tr>\n\t\t<td><b>dp</b></td>\n\t\t<td>...</td>\n\t\t<td><b>[ 0 ]</b></td>\n\t\t<td>0</td>\n\t\t<td>0 + 2 = 2</td>\n\t\t<td><b>dp</b></td>\n\t\t<td>...</td>\n\t\t<td><b>[ 2 ]</b></td>\n\t\t<td>0</td>\n\t\t<td>2 + 2 = 4</td>\n\t</tr>\n</table>\n\n4. *Condition b.* s[ i - 1 ] == \' **)** \' && s[ i ] == \' **)** \' means that **s[ i ]** could be a closing parentheses of the pattern \' **(** ( ... ) **)** \'.\nIn this case we already checked **s[ i - 1 ]** at the previous step and it could be a part of the previous valid or invalid substring, let\'s call it **sub<sub>i-1</sub>**. Also we have already put some value in **dp[ i - 1 ]**. Thus, only **s[ i ]** needs further investigation.\n* We have to check if the character before **sub<sub>i-1</sub>** equals \' **(** \'. To do that we subtract the value of **dp[ i - 1 ]** (the length of **sub<sub>i-1</sub>**) plus 1, from **i** to get the resulting equation **s[ i - (dp[ i - 1 ] + 1) ]**.\n* In this example, for **i = 7** we have to check the character at **i = 2**: s[ 7 - (4 + 1) ] => s[ 2 ] == \' **(** \', if ```true``` we will put in **dp[ i ] = 2 + dp [ i - 1] + dp[ i - (dp[ i - 1] + 2) ]**. The last term dp[ i - (dp[ i - 1] + 2) ] appears because we also have to check if there a valid substring just before the considering substring.\nThat is why in the considering example we get **8** at **dp[ 7 ]**: **2** (when we found the opening parentheses at i = 2) + **4** (the length of the **sub<sub>i-1</sub>** as it is valid) + **2** (the substring at i = 1 is also valid) = **8**.\n\n<h3 id="javascript-solution">JavaScript</h3>\n\n```\nfunction longestValidParentheses(s) {\n\t// maxLength variable is used to monitor the maximum length of the valid substring\n\t// every time we fall in condition a. or b.\n\t// by using it we don\'t need to find the maximum value in the resulting dp array\n    let maxLength = 0;\n    let dp = new Array(s.length).fill(0);\n    \n    for (let i = 1; i < s.length; i++) {\n        if (s[i - 1] === \'(\' && s[i] === \')\') { // - condition a.\n            dp[i] = 2 + (dp[i - 2] || 0); // - dp[i-2] can return undefined, if so we will add zero instead\n            maxLength = Math.max(maxLength, dp[i]);\n        }\n        if (\n            s[i - 1] === \')\' &&\n            s[i] === \')\' &&\n            s[i - dp[i - 1] - 1] === \'(\' // - condition b.\n        ) {\n            dp[i] = 2 + dp[i - 1] + (dp[i - dp[i - 1] - 2] || 0);\n            maxLength = Math.max(maxLength, dp[i]);\n        }\n    }\n    return maxLength;\n};\n```\n\n<h3 id="typescript-solution">TypeScript</h3>\n\n```\nfunction longestValidParentheses(s: string): number {\n\t// maxLength variable is used to monitor the maximum length of the valid substring\n\t// every time we fall in condition a. or b.\n\t// by using it we don\'t need to find the maximum value in the resulting dp array\n    let maxLength: number = 0;\n    let dp: number[] = new Array(s.length).fill(0);\n    \n    for (let i = 1; i < s.length; i++) {\n        if (s[i - 1] === \'(\' && s[i] === \')\') { // - condition a.\n            dp[i] = 2 + (dp[i - 2] || 0); // - dp[i-2] can return undefined, if so we will add zero instead\n            maxLength = Math.max(maxLength, dp[i]);\n        }\n        if (\n            s[i - 1] === \')\' &&\n            s[i] === \')\' &&\n            s[i - dp[i - 1] - 1] === \'(\' // - condition b.\n        ) {\n            dp[i] = 2 + dp[i - 1] + (dp[i - dp[i - 1] - 2] || 0);\n            maxLength = Math.max(maxLength, dp[i]);\n        }\n    }\n    return maxLength;\n};\n```
['Dynamic Programming', 'TypeScript', 'JavaScript']