Longest Palindromic Substring

Problem:

Longest Palindromic Substring

Given a string, find the longest palindromic substring in that string.

For example, given string "mqmqz"

Return "mqm" or "qmq".

Given string "hrrq"

Return "rr"

Solution:

Palindromic substring is symmetric around the center. With this property, the easiest way is to start the test from the center, then expand two sides until find asymmetric characters. There are two types of palindromic words, aba and aa. While aba has odd number of characters, the aa has even number of characters. So we can iterate the given string, for each position, we test the two types of palindromic substring centered at the current position. 

class Solution {
  public static void main(String...args) {
    System.out.println(longestPalindr("mqmqz"));
    System.out.println(longestPalindr("hrrq"));
  }
  public static String longestPalindr(String str) { //hrrq
    String result = "";
    for(int i = 0; i < str.length(); i++) {
      int l = i - 1;
      int r = i + 1;
      String tmp = str.substring(i, i+1);
      while(l > 0 && r < str.length() && str.charAt(l) == str.charAt(r)) {
        tmp = str.substring(l, r+1);
        l--;
        r++;
      }
      if(result.length() < tmp.length())
          result = tmp;
   
      l = i;
      r = i + 1;
      tmp = "";
      while(l > 0 && r < str.length() && str.charAt(l) == str.charAt(r)) {
        tmp = str.substring(l, r+1);
        l--;
        r++;
      }
      if(result.length() < tmp.length())
          result = tmp;
    }
    return result;
  }
}

The above solution created a lot of temporary substrings, which is not necessary. The following improvement get rid of the temporary substrings, and use the substrings' start and end index to represent them instead.

class Solution {
  public static void main(String...args) {
    System.out.println(longestPalindr("mqmqz"));
    System.out.println(longestPalindr("hrrq"));
  }
 
  private static int palindrLen(String str, int l, int r) {
    while(l > 0 && r < str.length() && str.charAt(l) == str.charAt(r)) {
      l--;
      r++;
    }
    return r - l - 1;
  }
  public static String longestPalindr(String str) { //hrrq
    int start = 0;
    int end = 0;
    for(int i = 0; i < str.length(); i++) {
      int len = Math.max(palindrLen(str, i, i), palindrLen(str, i, i+1));
      if(len > end - start + 1) {
        start = i - (len - 1)/2;
        end = i + len/2;
      }
    }
    return str.substring(start, end + 1);
  }
}

For each position, the test takes O(N) time complexity, there are N positions, so the total time complexity is O(N^2), the space complexity is O(1).