Problem 05 leetcode.. n^3 solution.

shekhargulati · shekhargulati · commit b03f89a84bb7 · 2016-04-01T23:24:16.000+05:30
diff --git a/java8/src/main/java/com/shekhargulati/leetcode/algorithms/Problem03.java b/java8/src/main/java/com/shekhargulati/leetcode/algorithms/Problem03.java
@@ -1,4 +1,4 @@
-package com.shekhargulati.leetcode;
+package com.shekhargulati.leetcode.algorithms;
 
 /**
  * Longest substring without repeating characters
diff --git a/java8/src/main/java/com/shekhargulati/leetcode/algorithms/Problem05.java b/java8/src/main/java/com/shekhargulati/leetcode/algorithms/Problem05.java
@@ -0,0 +1,45 @@
+package com.shekhargulati.leetcode.algorithms;
+
+import java.util.Objects;
+
+/**
+ * Given a string S, find the longest palindromic substring in S.
+ * You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
+ */
+public class Problem05 {
+
+    public static String longestPalindrome(final String input) {
+        /*
+         Algorithm:
+         1. Start from left and go toward right
+         2. For each char, pick the right most element if they are equal then take substring and compare both sides
+         3. If they are equal then we have the match.
+         4. Else move to next combination
+         */
+        String[] chars = input.split("");
+        String palindrome = null;
+        for (int i = 0; i < chars.length; i++) {
+            String left = chars[i];
+            for (int j = chars.length - 1; j > i; j--) {
+                String right = chars[j];
+                if (Objects.equals(left, right)) {
+                    String first = input.substring(i, j + 1);
+                    if (Objects.equals(first, reverse(first))) {
+                        if (palindrome == null || first.length() > palindrome.length()) {
+                            palindrome = first;
+                        }
+                    }
+                }
+            }
+        }
+        return palindrome;
+    }
+
+    private static String reverse(String in) {
+        char[] chrs = new char[in.length()];
+        for (int i = 0; i < in.length(); i++) {
+            chrs[in.length() - i - 1] = in.charAt(i);
+        }
+        return String.valueOf(chrs);
+    }
+}
diff --git a/java8/src/test/java/com/shekhargulati/leetcode/Problem03Test.java b/java8/src/test/java/com/shekhargulati/leetcode/Problem03Test.java
@@ -1,5 +1,6 @@
 package com.shekhargulati.leetcode;
 
+import com.shekhargulati.leetcode.algorithms.Problem03;
 import org.junit.Test;
 
 import static org.hamcrest.CoreMatchers.equalTo;
diff --git a/java8/src/test/java/com/shekhargulati/leetcode/algorithms/Problem05Test.java b/java8/src/test/java/com/shekhargulati/leetcode/algorithms/Problem05Test.java
@@ -0,0 +1,16 @@
+package com.shekhargulati.leetcode.algorithms;
+
+import org.junit.Test;
+
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.junit.Assert.assertThat;
+
+public class Problem05Test {
+
+    @Test
+    public void shouldDetectLongestPalindrome() throws Exception {
+        final String input = "saasdcjkbkjnjnnknvjfknjnfjkvnjkfdnvjknfdkvjnkjfdnvkjnvjknjkgnbjkngkjvnjkgnbvkjngfreyh67ujrtyhytju789oijtnuk789oikmtul0oymmmmmmmmmmmmmmmm";
+        String l = Problem05.longestPalindrome(input);
+        assertThat(l, equalTo("mmmmmmmmmmmmmmmm"));
+    }
+}

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,4 @@`
`1`		`-package com.shekhargulati.leetcode;`
	`1`	`+package com.shekhargulati.leetcode.algorithms;`
`2`	`2`
`3`	`3`	`/**`
`4`	`4`	`* Longest substring without repeating characters`