So I have been trying to solve Task C https://atcoder.jp/contests/abc286/tasks/abc286_c in Java. Here is what I came up with :-

     static long minCostToConvertToPalindrome(int a, int b, char[] word, int f, int s) {

        if (f >= s) {
            return 0;
        }

        String cacheKey = f + "-" + s;
        if (cache.containsKey(cacheKey))
            return cache.get(cacheKey);

        // Rotate the word
        int amountSpentInRotation = a + (word[f] == word[f + 1] ? 0 : b);

        // Change the word
        int amountSpentInChanging = word[f] == word[s] ? 0 : b;

        long minAmountSpent = Math.min(
                amountSpentInRotation + minCostToConvertToPalindrome(a, b, word, f + 2, s),
                amountSpentInChanging + minCostToConvertToPalindrome(a, b, word, f + 1, s - 1)
        );

        cache.put(cacheKey, minAmountSpent);
        return minAmountSpent;

    }

Note that I call the function like this -> minCostToConvertToPalindrome(a, b, word, 0, word.length - 1) in my main function.

Now, its clear that there are only N^2 possible combinations of parameters f and s. So the time complexity of my solution is also O(N^2) I think. The editorial also suggests a O(N^2) solution so why does mine not make it?

Please help me Thank you for reading