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!
Leandro Casuso

Leandro Casuso

· 11 days ago

We could improve the DP solution using the common approach of maintaining only the last needed rows (or diagonals if you use them instead of the rows). That will reduce the space to O(N).

S

singhursefamily

· a year 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
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, {})
Show 1 reply
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

· 5 years ago

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

Show 1 reply

Reading Progress

0%

Vote for new content