5. Longest Palindromic Substring

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

 

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters (lower-case and/or upper-case),

Rust Solution

struct Solution;

use std::iter::FromIterator;

impl Solution {
    fn longest_palindrome(s: String) -> String {
        let n = s.len();
        if n == 0 {
            return "".to_string();
        }
        let s: Vec<char> = s.chars().collect();
        let mut start = 0;
        let mut end = 0;
        for i in 0..n {
            let mut left = i;
            let mut right = i;
            while right + 1 < n && s[right + 1] == s[left] {
                right += 1;
            }
            while left > 0 && right < n - 1 && s[left - 1] == s[right + 1] {
                left -= 1;
                right += 1;
            }
            if right - left > end - start {
                start = left;
                end = right;
            }
        }
        String::from_iter(&s[start..=end])
    }
}

#[test]
fn test() {
    let s = "babad".to_string();
    let res = "bab".to_string();
    assert_eq!(Solution::longest_palindrome(s), res);
}

Having problems with this solution? Click here to submit an issue on github.