5. Longest Palindromic Substring Medium

1/**
2 * [5] Longest Palindromic Substring
3 *
4 * Given a string s, return the longest palindromic substring in s.
5 *  
6 * Example 1:
7 *
8 * Input: s = "babad"
9 * Output: "bab"
10 * Note: "aba" is also a valid answer.
11 *
12 * Example 2:
13 *
14 * Input: s = "cbbd"
15 * Output: "bb"
16 *
17 * Example 3:
18 *
19 * Input: s = "a"
20 * Output: "a"
21 *
22 * Example 4:
23 *
24 * Input: s = "ac"
25 * Output: "a"
26 *
27 *  
28 * Constraints:
29 *
30 * 1 <= s.length <= 1000
31 * s consist of only digits and English letters (lower-case and/or upper-case),
32 *
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/longest-palindromic-substring/
37// discuss: https://leetcode.com/problems/longest-palindromic-substring/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40impl Solution {
41    pub fn longest_palindrome(s: String) -> String {
42        let mut result = "".to_string();
43        for i in 0..s.len() {
44            let odd = Self::check_palindrome(&s, i, i);
45            if odd.len() > result.len() {
46                result = odd;
47            }
48            let even = Self::check_palindrome(&s, i, i + 1);
49            if even.len() > result.len() {
50                result = even;
51            }
52        }
53        result
54    }
55
56    fn check_palindrome(x: &String, mut s: usize, mut e: usize) -> String {
57        while e < x.len() && x[s..s + 1] == x[e..e + 1] {
58            if s == 0 {
59                return x[s..e + 1].to_owned();
60            }
61            s -= 1;
62            e += 1;
63        }
64        if s + 1 < e {
65            x[s + 1..e].to_owned()
66        } else {
67            "".to_owned()
68        }
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_5() {
80        assert_eq!(
81            Solution::longest_palindrome("babad".to_string()),
82            "bab".to_owned()
83        );
84        assert_eq!(
85            Solution::longest_palindrome("a".to_string()),
86            "a".to_owned()
87        );
88    }
89}
90