## Editorial for HHPC1 P1 - Yielding the Longest Substring

**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:

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

The answer will simply be the , where is the length of the longest substring of identical characters.

Time complexity: .

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

Find the positions that satisfy the condition and . For each of these positions , iterate to the left to find the farthest position , where all characters , , , , are the same. Similarly, iterate to the right to find the farthest position , where all characters , , , , are the same. The answer will be the 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 .

Overall time complexity for each test case: .

## Comments