Самая длинная палиндромная подстрока в Java

Проблема

Самая длинная палиндромная подстрока

Решение

Время O(n^2), Пространство O(1)

public String longestPalindrome(String s) {
   if (s.isEmpty()) {
      return null;
   } 
   if (s.length() == 1) {
      return s;
   } 
   String longest = s.substring(0, 1);
   for (int i = 0; i < s.length(); i++) {
      // get longest palindrome with center of i
      String tmp = helper(s, i, i);
      if (tmp.length() > longest.length()) {
         longest = tmp;
      }
      // get longest palindrome with center of i, i+1
      tmp = helper(s, i, i + 1);
      if (tmp.length() > longest.length()) {
         longest = tmp;
      }
   } 
   return longest;
}
// Given a center, either one letter or two letter, 
// Find longest palindrome
public String helper(String s, int begin, int end) {
   while (begin >= 0 && end <= s.length() 
                  - 1 && s.charAt(begin) == 
                   s.charAt(end)) {
      begin--;
      end++;
   }
   return s.substring(begin + 1, end);
}

Существует более эффективный способ решения этой проблемы с помощью алгоритма Манахера.
Алгоритм Манахера гораздо сложнее понять, хотя
он дает преимущества временной сложности O(n).
> Этот алгоритм определенно нетривиален, и вы не должны
придумывать такой алгоритм во время собеседования.

Подробнее: http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/