solve: 05_longest-palindromic-substring

god i fucking hate this. lots of hit & trial
on this one specially. instant fixing right after
failing a test without thinking aot.

2 files changed, 70 insertions, 1 deletions

diff --git a/05_longest-palindromic-substring/Cargo.lock b/05_longest-palindromic-substring/Cargo.lock
new file mode 100644
index 0000000..6f94d4a
--- /dev/null
+++ b/05_longest-palindromic-substring/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 4
+
+[[package]]
+name = "longest-palindromic-substring"
+version = "0.1.0"
diff --git a/05_longest-palindromic-substring/src/main.rs b/05_longest-palindromic-substring/src/main.rs
index e7a11a9..01300ef 100644
--- a/05_longest-palindromic-substring/src/main.rs
+++ b/05_longest-palindromic-substring/src/main.rs
@@ -1,3 +1,65 @@
 fn main() {
-    println!("Hello, world!");
+    let s = "abcda".to_string();
+    dbg!(Solution::longest_palindrome(s));
+}
+
+struct Solution(());
+
+impl Solution {
+    pub fn longest_palindrome(s: String) -> String {
+        use std::collections::HashMap;
+
+        if s.len() == 1 {
+            return s;
+        }
+        let s = s.chars().collect::<Vec<char>>();
+        if s.len() == 2 {
+            if s[0] != s[1] {
+                return s[0].to_string();
+            } else {
+                return s.into_iter().collect::<String>();
+            }
+        }
+
+        let mut hm: HashMap<char, Vec<usize>> = HashMap::new();
+        let mut ls = s[0].to_string();
+
+        for (idx, c) in s.iter().enumerate() {
+            if let Some(indices) = hm.get(&c) {
+
+                for c_idx in indices.iter() {
+                    let ss = &s[*c_idx..=idx];
+                    if Self::is_palindrome(ss) && ss.len() > ls.len() {
+                        ls = ss.clone().into_iter().collect::<String>();
+                    }
+                }
+
+                hm.entry(*c)
+                .and_modify(|v| v.push(idx));
+
+            } else {
+                hm.insert(c.clone(), vec![idx]);
+            }
+        }
+
+        ls
+    }
+
+    pub fn is_palindrome(slice: &[char]) -> bool {
+        if slice.len() == 2 {
+            return &slice[0] == &slice[1];
+        }
+
+        let mut l = 0;
+        let mut r = slice.len() - 1;
+
+        while l < r {
+            if slice[l] != slice[r] {
+                return false;
+            }
+            l += 1;
+            r -= 1;
+        }
+        return true;
+    }
 }