saved_chats/#29000

USER: https://codeforces.com/problemset/problem/1492/C

BOT: Thanks! Now could you provide a link to the editorial.



USER: https://codeforces.com/blog/entry/87792

BOT: Would you like hints to help you solve the problem or an interactive explanation of the editorial (hint/editorial)? 



USER: editorial

BOT: For some subsequence of the string $$$s$$$, let $$$p_i$$$ denote the position of the character $$$t_i$$$ in the string $$$s$$$. For fixed $$$i$$$, we can find a subsequence that maximizes $$$p_{i + 1} - p_i$$$. 
Let $$$\textit{left}_{i}$$$ and $$$\textit{right}_{i}$$$ be the minimum and maximum possible value of $$$p_i$$$ among all valid $$$p$$$s. Now, it is easy to see that the maximum possible value of $$$p_{i+1} - p_{i}$$$ is equal to $$$\textit{right}_{i + 1} - \textit{left}_{i}$$$. 
To calculate $$$\textit{left}_i$$$ we just need to find the first element after $$$\textit{left}_{i - 1}$$$ which is equal to $$$t_i$$$. This can be done by a simple greedy or dp algorithm. $$$\textit{right}_i$$$ can be found in the same way. 
So, after finding $$$\textit{left}$$$ and $$$\textit{right}$$$, the answer is $$$\max_{i=1}^{i=n-1} \textit{right}_{i + 1} - \textit{left}_i$$$.
Complexity: $$$O(n + m)$$$.
Let me know if you have any questions.