Grokking LinkedIn Coding Interview
Vote

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
G

Gary

· 4 years ago

Why does the bottom up solution here start with startIndex at n - 1 instead of 0, like in the Longest Common Substring/Subsequence problems in chapter 6?

Show 1 reply
M

Mircea C

· 4 years ago

For the memoisation tecgnique, isn’t the time complexity still 2^n? We still have 2^n function calls...

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findLPSLength(self, st):
    
    def is_palindrom(s):
      i = 0
      j = len(s) - 1
      while i <= j:
        if s[i] != s[j]:
          return False
        i += 1
        j -= 1
      return True
    
    def dp(index, s, memo):
      if s in memo:
        return memo[s]

      if is_palindrom(s):       
        return len(s)

      if index >= len(s):
        return 0

      skip_char = dp(index + 1, s[:], memo)

      with_char = dp(index + 1, s[:index] + s[index+1:], memo)

      result = max(skip_char, with_char)

      memo[s] = result
      
      return result

    return dp(0, st, {})
S

singhursefamily

· 9 months ago

The two dynamic programming solutions have time and space complexity both of O(N^2).

I found a solution that also has a time complexity of O(N^2) but reduces the space complexity to O(1). It uses a two pointer approach. The code in in Javascript.

findLPSLength(str) {
    // two pointers, one on each end of `str`
    let left = 0;
    let right = str.length - 1;
    
    // size of the palindrome. this is the function output.
    let size = 0;

    while (left < right) {
      const target = str[left];
      let r;

      for (r = right; r > left; r -= 1) {
        const consider = str[r];
        if (target === consider) {
          size += 2;
          break;
        }
      }

      // move right pointer only if a match was found.
      // (r will be greater than left