Type Here to Get Search Results !

Longest Palindromic Substring leetcode solution.

0

 Longest Palindromic Substring leetcode solution. 

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.


Example 2:

Input: s = "cbbd"
Output: "bb"
 

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.


class Solution 
{
  public String longestPalindrome(String s)
  {
      // O(n^3) time | O(n) space
      String res = "";
      String tmp = "";
      int n = s.length();
      
      for(int i = 0; i < n; i++)
      {
          for(int j = i; j < n; j++)
          {
              // j has to equal i. Otherwise, we miss the case when s = "a"
              tmp = s.substring(i, j+1);
              
              if(isPalindrome(tmp) && tmp.length() > res.length())
                  res = tmp;
          }
      }
      return res;
  }
  
  public boolean isPalindrome(String str)
  {
      int left = 0, right = str.length()-1;
      
      while(left < right)
      {
          if(str.charAt(left) != str.charAt(right))
              return false;
          
          left++;
          right--;
      }
      return true;
  }
}



Post a Comment

0 Comments