Another Solution: Longest Palindrome Substring

class Solution(object): def __init__(self): self.lookup = {“test”} def isPalindrome(self, s, i, k): j = i + k – 1 if s[i] == s[j]: key = self.createKey(i + 1, j – 1) if key in self.lookup: #self.lookup.remove(key) return True return False def createKey(self, i, j): #return “{}:{}”.format(i,j) #return (i, j) #key = bin(i) + bin(j) #return … More Another Solution: Longest Palindrome Substring

Longest Palindrome Substring in a String

DP based solution class Solution(object): def __init__(self): self.lookup = {} def isPalindrome(self, s, dp, i, k): j = i + k – 1 if s[i] == s[j] and dp[i + 1][j – 1]: return True return False def longestPalindrome(self, s): “”” :type s: str :rtype: str “”” size = len(s) if size < 2: return … More Longest Palindrome Substring in a String

Union-Find Problem

The problem is to find if a given edge (a, b) is connected in a graph with vertices {a, b, c, …}. Naive Solution – O(n^2) Maintain a parent array of size (len of vertex array) Update an edge (a, b) with the index a & b in the vertex array ParentArray[a] = b ParentArray[b] … More Union-Find Problem

Longest Substring without Repeating Characters

The solution uses a sliding window and uses O(n) time and O(n) space. There are many cases to take care of. We can skip the process string less than size 2. Iterate the string, checking each char as key in the hash, adding if not present. If not present in hash, add each char as … More Longest Substring without Repeating Characters