Is there a more elegant way to solve this anti-palindrome problem?

Question

Problem source: Anti-Palindrome from Kattis

Summary

The problem requires determining if a given line of text contains any palindromes (substrings of two or more characters that read the same forwards and backwards, ignoring spaces, punctuation, and case). If any palindrome exists, the output should be "Palindrome"; otherwise, the output should be "Anti-palindrome". Non-alphabetic characters must be ignored, and uppercase/lowercase differences are treated as the same. The input will have at least one alphabetic character and be at most 80 characters long.

Input

1. Length of input text: 1 to 80 characters.
2. Content: At least one alphabetic character, but it may also contain spaces, punctuation, and other non-alphabetic characters.

Output

• "Palindrome" if the text contains any palindromes (substrings of at least 2 alphabetic characters that are palindromic after ignoring non-alphabetic characters and case).
• "Anti-palindrome" if no such palindrome exists.

My Solution

panlindrome()

This bool type function is used to decide whether a substring of str (from start to end inclusive) is a palindrome or not)

bool panlidrome(char *str, long start, long end)
{
  if (start >= end)
  {
    return true;
  }
  if (!isalpha(str[start]))
  {
    return panlidrome(str, start + 1, end);
  }
  if (!isalpha(str[end]))
  {
    return panlidrome(str, start, end - 1);
  }
  if (tolower(str[start]) != tolower(str[end]))
  {
    return false;
  }
  return panlidrome(str, start + 1, end - 1);
}

main()

The main function, mainly use two loops to check all the substrings of the input line. Suppose that the non-standard input/output functions work finely.

int main()
{
  char *line = cs1010_read_line();
  if (line == NULL)
  {
    return 1;
  }
  long len = (long)strlen(line) - 1; // -2 to avoid the \n
  for (long start = 0; start < len - 2; start += 1)
  {
    for (long end = start + 2; end < len; end += 1)
    {
      if (panlidrome(line, start, end))
      {
        cs1010_println_string("Palindrome");
        free(line);
        return 0;
      }
    }
  }
  cs1010_println_string("Anti-palindrome");
  free(line);
}

For my question, I am not sure whether there will be a more elegant way, either in the improvement of efficiency or the neatness of the code, to solve this problem!

Thanks!

Answer 1

Keep track of the last two alphabetic characters that you encounter. If the current character is one of these two, you have a small palindrome. As larger palindromes consist of smaller palindromes, you only need to check for the smaller ones, i.e. with length 2 or 3:

bool has_palindrome(char *str)
{
    size_t len = strlen(str);
    char prev = ' ', prevPrev = ' '; // Initialised with non-alpha characters
    for (size_t i = 0; i < len; i++) {
        char c = tolower(str[i]); // Ignore case
        if (!isalpha(c)) continue; // Ignore punctuation, spaces, ...etc
        if (c == prev || c == prevPrev) return true;
        prevPrev = prev;
        prev = c;
    }
    return false;
}

In your main, you would just call this function once:

    cs1010_println_string(has_palindrome(line) ? "Palindrome" : "Anti-palindrome");