[DAY13]Special String Again
Solution 1: Generate all the possible substrings and traverse all of them to check if the special requirements are fulfilled. This method would be inefficient and the time complexity would be O(N³).
Solution 2: Every character of the input string could form a substring which satisfies the first requirement: all of the characters are the same, e.g. aaa. So we traverse back to the head of the string until we get a different character. Each identical character we met would form a substring which satisfies requirement number one. If a character is different from previous character, then it might be able to form a substring which satisfies the second requirement: all characters except the middle one are the same, e.g. aadaa. So we traverse not only to the head of the string but also the tail of the string until the left-side character is different from right-side character.