5. Longest Palindromic Substring.md

5. Longest Palindromic Substring

---

Difficulty : Medium

Related Topics : String、Dynamic Programming

---

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

---

Solution

• mine
  • Java
    • Runtime: 5 ms, faster than 97.10%, Memory Usage: 36 MB, less than 100.00% of Java online submissions

      // O(n^2)time
      // O(1)space
      public int maxLen,left;
      public String longestPalindrome(String s) {
          if(s == null || s.length() < 2){
              return s;
          }
          for(int i = 0; i < s.length(); i++){
              //maxLen为奇数  aba
              checkPalindromic(s,i,i);
              //maxLen为偶数  aa
              checkPalindromic(s,i,i+1);
          }
          return s.substring(left, left + maxLen);
      }
      
      public void checkPalindromic(String s, int start, int end){
          while(start>=0 && end + 1 <= s.length() && s.charAt(start) == s.charAt(end)){
              start--;
              end++;
          }
      
          //S abcdcde
          //start 3 end 3
          //start 2 end 4
          //start 1 end 5
          // maxLen = end - start - 1 =  5 - 1 -1
          if(maxLen < end - start - 1){
              maxLen = end - start - 1;
              left = start + 1;
          }
      }
      

---

• the most votes

• Runtime: 5 ms, faster than 97.10%, Memory Usage: 35.9 MB, less than 100.00% of Java online submissions

  private int lo, maxLen;
  
  public String longestPalindrome(String s) {
      int len = s.length();
      if (len < 2)
          return s;
  
      for (int i = 0; i < len-1; i++) {
          extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
          extendPalindrome(s, i, i+1); //assume even length.
      }
      return s.substring(lo, lo + maxLen);
  }
  
  private void extendPalindrome(String s, int j, int k) {
      while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
          j--;
          k++;
      }
      if (maxLen < k - j - 1) {
          lo = j + 1;
          maxLen = k - j - 1;
      }
  }
  

---