Что является Большой О этой реализации

Question

Я пытаюсь ответить на вопрос по leetcode https://leetcode.com/problems/palindromic-substrings/. Я знаю, что решение прохождения - это решение O (N ^ 2) с динамическим программированием c. Все решения, которые я видел, использовали восходящий подход. Я пытался использовать нисходящий подход, и я думал, что я также выполнил O (N ^ 2), но онлайн-судья выдает мне ошибку превышения лимита времени в последнем тестовом примере, что заставило меня сомневаться, действительно ли моя реализация O (N ^ 2). Может кто-нибудь сказать мне правильный большой O из приведенного ниже кода?

bool dfs(string s, int start, int end, string curWord, int &count, unordered_map<string, int> &map)
{
    if (start >= end)
    {
        return true;
    }
    string st = to_string(start) + " , " + to_string(end);
    if (map.find(st) != map.end())
        return map[st];

    if (s[start] == s[end] && dfs(s, start + 1, end - 1, curWord, count, map))
    {
        count++;
        map[st] = true;
    }
    else
    {
        map[st] = false;
    }
    return map[st];
}

int countSubstrings(string s)
{
    string word = "";
    int count = 0;
    unordered_map<string, int> map;

    for (int i = 0; i < s.length(); i++)
    {
        for (int j = s.length() - 1; j > i; j--)
        {
            dfs(s, i, j, word, count, map);
        }
    }
    return count + s.length();
}