-
Notifications
You must be signed in to change notification settings - Fork 1
/
LongestPalindromicSubstring.java
44 lines (40 loc) · 1.21 KB
/
LongestPalindromicSubstring.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package com.leetcode;
public class LongestPalindromicSubstring {
//https://leetcode.com/problems/longest-palindromic-substring/
//Expand at each location O(n^2)
/**
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
**/
class Solution {
int l;
int r;
int max = 0;
public String longestPalindrome(String s) {
if(s == null || s.length() == 0) return "";
if(s.length() == 1) return s;
for(int i = 0 ; i < s.length() ; i++){
findLongestPalindromicSubstring(s,i,i+1);
findLongestPalindromicSubstring(s,i,i);
}
return s.substring(l,r);
}
public void findLongestPalindromicSubstring(String s, int left, int right ){
while(left>=0 && right< s.length() && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
int len = right - left - 1;
if(len > max){
max = len;
this.l = left+1;
this.r = right;
}
}
}
}