longest palindrome substring

sherxon · Jun 28, 2018 · 1414b75 · 1414b75
1 parent 123d80c
commit 1414b75
Show file tree

Hide file tree

Showing 3 changed files with 78 additions and 0 deletions.
diff --git a/src/AmazonDemo/Coin.java b/src/AmazonDemo/Coin.java
@@ -0,0 +1,28 @@
+package AmazonDemo;
+
+/**
+ * Why Did you create this class? what does it do?
+ * Given an innnite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and
+ * pennies (1 cent), write code to calculate the number of ways of representing n cents.
+ */
+public class Coin {
+    static int count = 0;
+
+    public static void main(String[] args) {
+        int[] a = new int[] { 5, 10, 25 };
+        go(a, 0, 20);
+        System.out.println(count);
+    }
+
+    private static void go(int[] a, int k, int n) {
+        if (n < 0 || k >= a.length)
+            return;
+        if (n == 0) {
+            count++;
+        }
+        for (int i = k; i < a.length; i++) {
+            go(a, i, n - a[i]);
+        }
+    }
+
+}
diff --git a/src/problems/Medium.txt b/src/problems/Medium.txt
@@ -2728,3 +2728,16 @@ Note:
 1 <= rooms.length <= 1000
 0 <= rooms[i].length <= 1000
 The number of keys in all rooms combined is at most 3000.
+
+186)Longest Palindromic Substring
+Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
+
+Example 1:
+
+Input: "babad"
+Output: "bab"
+Note: "aba" is also a valid answer.
+Example 2:
+
+Input: "cbbd"
+Output: "bb"
diff --git a/src/problems/medium/LongestPalindromicSubstring.java b/src/problems/medium/LongestPalindromicSubstring.java
@@ -0,0 +1,37 @@
+package problems.medium;
+
+/**
+ * Why Did you create this class? what does it do?
+ */
+public class LongestPalindromicSubstring {
+    public String longestPalindrome(String s) {
+        if (s == null || s.length() == 0)
+            return s;
+        String max = String.valueOf(s.charAt(0));
+        char[] a = s.toCharArray();
+        for (int i = 0; i < s.length(); i++) {
+            int[] p1 = pal(a, i, i);
+            if (p1[1] - p1[0] > max.length()) {
+                max = s.substring(p1[0], p1[1]);
+            }
+            p1 = pal(a, i, i + 1);
+            if (p1[1] - p1[0] > max.length()) {
+                max = s.substring(p1[0], p1[1]);
+            }
+
+        }
+        return max;
+    }
+
+    int[] pal(char[] a, int i, int j) {
+
+        while (i >= 0 && j < a.length) {
+            if (a[i] != a[j]) {
+                return new int[] { i + 1, j };
+            }
+            i--;
+            j++;
+        }
+        return new int[] { i + 1, j };
+    }
+}