Mock interview -

Leetcode palindrome pairs

https://leetcode.com/problems/palindrome-pairs/discuss/
    */
    
    battab -> [0, 1]
    taabbat -> [1, 0]
    
    keywords:  unique words, 
  ask: indices (i, j), words[i] + words[j] is palindrome
  
  Brute force: n - length of words array  n * (n - 1) - > O(N^2) - pair to check, but each word we need to spend time to check if palindrome
  O(n) -> even/ odd -> center -> move to two end and check if it is palindrome
  
  -> sort the array
  
  [bat, cat, tab] -O(nlogn)  save
  -> original index -> 
    
  if two words are palindrome -> length is same, then we know that it should be reverse of the word 
    
    example 2: [0, 1] -> reverse two words
    
    [3, 2]  -> 3, 1 -> lls -> s  palindrome  lls -> s 
    lls   3, 4 sssll -> we can tell -> short one -> reverse sll -> it is substring of the another one -> remove substring, left over is palindrome ss -> 
      
  sll -> sssll 
      
  Trie -> reduce time complexity - check prefix/ suffix