First a little background, I started doing leetcode only about two monthes ago with basically 0 knowledge of DSA, so if this sounds a bit amature to anyone, please go easy on me, I'm new to sweatin it out.

I'm making my way through Blind 75, and for the easy questions I basically came to the conclusion that a general rule of thumb is don't try to submit anything of O(N^2) time complexity, try to make everything O(N) or better. Of course as I progressed to mediums I found out that this is just a rule of thumb and that there are some problems with irreducible time complexity (can't do better than O(N^2). Or if you want to be technical, if there is a solution of better time complexity then no one has discovered it yet.

Take for example the problem longest palindromic substring (https://leetcode.com/problems/longest-palindromic-substring/submissions/). I tried for 30 minutes to think of solution with O(N) time complexity, and I just couldn't do it. My solution, which I've attached at the end of this post, runs in the 94 precentile for runtime, maxing out at around 300 ms. I was surprised because of the bad heuristic I mentioned earlier. How was an O(N^2) solution preforming so well? I'm clearly not smart enough to understand what I'm doing right here.

So I've come to accept that there are some questions where the best solution just can't go below O(N^2). And I'm fine with that. My question is then, how do we know if we can't reduce the time complexity. And if we can't know, then what are some good heuristics for identifying a problem that we think can't be reduced?

I've run into three problems today where I've psyched myself out, having soft-drafted the correct solution, only to get pissed at myself for not being able to reduce it down to an O(N) problem. And then I look at the solution and I'm just mad at myself for not having tried the idea that's written in O(N^2). Any guidance would be appreciated.

Some intuitions I've had:

1. Problems must be solved in O(N^2) iff it is made up of subproblems in O(N), and iff those subproblems can't be solved in constant time. (e.g. Three Sum)
2. ... Iff it requires reference to items in other indicies, and there's no way to get around it. (e.g. Longest Palindromic Substring, you need to reference the substrings to the left and to the right of the palindrome that you find, see my answer)
3. The problem requires sorting to solve, (e.g. Group Anagrams)

Thanks in advance.

My code:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        #O(n^2) solution, run a check for a window of 2 and then a window of 3, 
        #then check if there are any palindrones existing, 
        #if true check a little to the left and a little to the right for longer palindrones.
        
        if len(s) <= 1 or s == s[::-1]:
            return s
        
        max_palin = s[0]
    
        for i in range(1, len(s)):
            
            if s[i] == s[i - 1]:
                
                l = i - 1
                r = i
  
                while l >= 0 and r < len(s) and s[l] == s[r]:
                    
                    if len(max_palin) < r - l + 1:
                        max_palin = s[l:r+1]
                    
                    l -= 1
                    r += 1
        
        for i in range (2, len(s)):
            
            if s[i] == s[i - 2]:

                l = i - 2
                r = i
                
                while l >= 0 and r < len(s) and s[l] == s[r]:
                    
                    if len(max_palin) < r - l + 1:
                        max_palin = s[l:r+1]
                        
                    l -= 1
                    r += 1
        
        return max_palin