都2025了，居然有公司强制18点20下班，禁止加班。。。

那么问题来了，我们怎么高效地找出所有的回文子串呢？

最暴力的方法当然是遍历所有的子串，然后检查它是不是回文。这种方法的时间复杂度是 (O(n^3)) 的，因为：

1. 枚举所有的子串，起点 (i) 可以从 0 到 (n-1)，终点 (j) 可以从 (i) 到 (n-1)，这样就有 (O(n^2)) 级别的子串需要检查。
2. 对于每个子串，判断它是不是回文需要 (O(n)) 的时间。

这样的复杂度，在字符串长度稍微大一点时就会超时，所以肯定得优化。

优化的方法有两个：

1. 动态规划 （DP）：使用一个二维数组 dp[i][j] 表示从 i 到 j 这一段是不是回文。通过递推公式 dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]) 来优化判断过程，时间复杂度降到了 (O(n^2))。
2. 中心扩展 （Expand Around Center）：回文的中心可以是一个字符（奇数长度的回文），也可以是两个字符（偶数长度的回文）。我们遍历每个位置，把它当成回文中心，往两边扩展，找到所有可能的回文，时间复杂度也是 (O(n^2))，但空间复杂度更低。

Java 代码实现

这里选择 中心扩展 的方法，因为它更简单，空间复杂度只有 (O(1))：

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;

        for (int i = 0; i             count += expandFromCenter(s, i, i);   // 以单个字符为中心
            count += expandFromCenter(s, i, i+1); // 以两个字符为中心
        }

        return count;
    }

    private int expandFromCenter(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right             count++;
            left--;
            right++;
        }
        return count;
    }
}

代码解析：

• countSubstrings 方法遍历字符串中的每个字符，并把它作为回文的中心点。
• expandFromCenter 这个辅助方法从中心点出发，向两边扩展，直到不是回文为止，每找到一个回文就增加计数。
• 需要注意的是，回文的中心可能是一个字符（如 "aba" ），也可能是两个字符（如 "abba" ），所以要分别考虑 expandFromCenter(s, i, i) 和 expandFromCenter(s, i, i+1) 两种情况。