Commiting files for 08/06

surajr · surajr · commit ea154c679e0e · 2017-08-06T15:06:55.000-07:00
diff --git a/README.md b/README.md
@@ -29,6 +29,7 @@ Feel free to add issues, comment and pull request.
 |---------------- |---------------- | ----------- | --------------- | --------------- | ------------- |-----|
 | Leetcode  | [557. Reverse Words in a String III](https://leetcode.com/problems/reverse-words-in-a-string-iii/) | [Java](./java/reverseWords.java) \| [Python](./Python/) | _O(n)_       | _O(1)_          |  Easy       |         |
 | Leetcode  | [387. First Unique Character in a String](https://leetcode.com/problems/first-unique-character-in-a-string/) | [Java](./java/FirstUniqChar.java) \| [Python](./Python/) | _O(n)_       | _O(n)_          |  Easy       |         |
+| Leetcode  | [647. Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/) | [Java](./java/CountSubstrings.java) \| [Python](./Python/) | _O(n^2)_       | _O(1)_          |  Easy       |         |
 
 ## HashMap
 | Website 		| Title           |  Solution    |  Time           | Space           | Difficulty    |  Note| 
@@ -42,3 +43,9 @@ Feel free to add issues, comment and pull request.
 | Leetcode  | [152. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) | [Java](./java/MaximumProductSubArray.java) \| [Python](./Python/) | _O(n)_       | _O(1)_          |  Medium      |         |
 | Leetcode  | [628. Maximum Product of Three Numbers](https://leetcode.com/problems/maximum-product-of-three-numbers) | [Java](./java/MaximumProduct.java) \| [Python](./Python/) | _O(n)_       | _O(1)_          |  Easy      |         |
 | Leetcode  | [62. Unique Paths](https://leetcode.com/problems/unique-paths/) | [Java](./java/UniquePaths.java) \| [Python](./Python/) | _O(m*n)_       | _O(m+n)_          |  Easy      |         |
+
+
+## Recursion
+| Website 		| Title           |  Solution    |  Time           | Space           | Difficulty    |  Note| 
+|---------------- |---------------- | ----------- | --------------- | --------------- | ------------- |-----|
+| Leetcode  | [654. Maximum Binary Tree](https://leetcode.com/contest/leetcode-weekly-contest-44/problems/maximum-binary-tree/) | [Java](./java/654. Maximum Binary Tree) \| [Python](./Python/) | _O(n log n)_       | _O(n)_          |  Easy       |         |
diff --git a/java/ConstructMaximumBinaryTree.java b/java/ConstructMaximumBinaryTree.java
@@ -0,0 +1,49 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+public class Solution {
+    public TreeNode constructMaximumBinaryTree(int[] nums) 
+    {
+        //Recursive helper function
+        return helper(nums,0,nums.length-1);    
+    }
+    
+    public TreeNode helper(int [] nums, int low, int high)
+    {
+        if(high < low)
+            return null;
+        
+        //Identify the maximum element's index
+        int maxIndex = getMaxIndex(nums, low, high);        
+        
+        //Construct the root node
+        TreeNode root = new TreeNode(nums[maxIndex]);
+        
+        //Generate the left sub tree from the left part of sub array
+        root.left = helper(nums,low, maxIndex-1);
+        
+        //Generate the right sub tree from the right part of sub array
+        root.right = helper(nums, maxIndex+1, high);
+        
+        //Return the root
+        return root;
+    }
+    
+    public int getMaxIndex(int [] nums, int low, int high)
+    {
+        //Identify the maximum element's index to construct the root element
+        int maxIndex = low;
+        for(int i = low+1; i <= high; i++)
+        {
+            if(nums[i] > nums[maxIndex])
+                maxIndex = i;
+        }
+        return maxIndex;
+    }
+}
diff --git a/java/CountSubstrings.java b/java/CountSubstrings.java
@@ -0,0 +1,24 @@
+public class Solution 
+{
+    // This problem is exactly similar to longest palindromic substring. Just need to add count++.
+    // Generate all the substrings of a string and expand around the centre to see if it formas a palindrome
+    private int count = 0;
+    
+    public int countSubstrings(String s) 
+    {
+        for(int i=0; i<s.length(); i++)
+        {
+            isPalindrome(i,i,s); //Even length
+            isPalindrome(i,i+1,s); //Odd length
+        }
+        return count;
+    }
+    
+    public void isPalindrome(int left, int right, String s)
+    {
+        while(left >=0 && right < s.length() && s.charAt(left) == s.charAt(right))
+        {
+            count++; left--; right++;
+        }         
+    }
+}
