BOJ. Palindrome Is Not A Palindrome (15927)

On this page

Link

Key observation

Find the longest substring of S that is not a palindrome. If the whole string is not a palindrome, the answer is N. If it is a palindrome and all characters are identical, every substring is a palindrome, so the answer is -1. Otherwise, the answer is N - 1.

Proof

If the whole string is not a palindrome, S itself is a non-palindromic substring of length N, so the answer is N. If the whole string is a palindrome and all characters are identical, every substring consists of identical characters and is therefore a palindrome; the answer is -1.

Now suppose S is a palindrome but its characters are not all identical. The only substring of length N is S, so no non-palindromic substring can be longer than N. The only substrings of length N - 1 are obtained by removing the first or last character. Since S is a palindrome, these two strings are reversals of each other, so if one is a palindrome, the other is too.

Suppose both were palindromes. In particular, the prefix obtained by removing the last character would be a palindrome. Symmetry of the full string gives S[i] = S[N - 1 - i], while symmetry of that prefix gives S[i] = S[N - 2 - i]. Thus, for i = 0, …, N - 2, S[N - 1 - i] = S[N - 2 - i]. These equalities cover every adjacent pair, forcing all characters to be identical, a contradiction. Therefore both length-N - 1 substrings are non-palindromes, and the answer is N - 1.

One scan checks whether the string is a palindrome and whether all its characters are identical. The time complexity is O(N), and the extra space complexity beyond the input string is O(1).

C++17 implementation

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    const int n = static_cast<int>(s.size());
    bool isPalindrome = true;
    bool allSame = true;

    for (int i = 0; i < n; ++i) {
        if (s[i] != s[n - 1 - i]) isPalindrome = false;
        if (s[i] != s[0]) allSame = false;
    }

    if (!isPalindrome) cout << n << '\n';
    else if (allSame) cout << -1 << '\n';
    else cout << n - 1 << '\n';

    return 0;
}