## 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() {