Longest Palindromic Substring

Question 1

What are the inputs and outputs?

Answer 1

input: string
output: string of valid palindrome

Question 2

Is there an edge case?

Answer 2

Input is less than value of 1

Question 3

What is your approach?

Answer 3

• Create start and end variable
• Create expandAroundChar function that checks the left and right of a char to see if they match
• Create a for loop of s
  
  • check for odd palindrome and even palindrome
  • compare left and right then set new indexes for start and end variable if more than initial value
• return substring of start and end

Question 4

What is the time complexity?

Answer 4

O(n^2)
- iterating over each character is o(n)
- expandingAroundChar is o(n) because we expand outwards until we reach end of string
- since we have 2 potential centers(odd & even strings) it becomes O(n^2)

Question 5

What is the space complexity?

Answer 5

O(1)
- no data structures used