Editorial for HHPC1 P1 - Yielding the Longest Substring

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AustinJiang

Case 1 (Increasing the length of a substring of identical characters by one):

The answer will simply be the $max(N, L+1)$ ~max(N, L+1)~, where $L$ ~L~ is the length of the longest substring of identical characters.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~.

Case 2 (Replacing a letter to connect two substrings of identical characters on the sides):

Find the positions that satisfy the condition $a[i-1] == a[i+1]$ ~a[i-1] == a[i+1]~ and $a[i] != a[i-1]$ ~a[i] != a[i-1]~. For each of these positions $i$ ~i~, iterate to the left to find the farthest position $l$ ~l~, where all characters $S[l]$ ~S[l]~, $S[l+1]$ ~S[l+1]~, $\dots$ ~\dots~, $S[i-2]$ ~S[i-2]~, $S[i-1]$ ~S[i-1]~ are the same. Similarly, iterate to the right to find the farthest position $r$ ~r~, where all characters $S[i+1]$ ~S[i+1]~, $S[i+2]$ ~S[i+2]~, $\dots$ ~\dots~, $S[r-1]$ ~S[r-1]~, $S[r]$ ~S[r]~ are the same. The answer will be the $max(r-l+1)$ ~max(r-l+1)~ among these positions.

Since each subarray with identical characters will only be iterated from the left or the right, it can be proven that the total time complexity does not exceed $\mathcal{O}(2N)$ ~\mathcal{O}(2N)~.

Overall time complexity for each test case: $\mathcal{O}(3N)$ ~\mathcal{O}(3N)~.

Comments

There are no comments at the moment.