Задача: 647. Palindromic Substrings
Сложность: medium

Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.

Пример:

Input: s = "abc"
Output: 3

👨‍💻 Алгоритм:

1⃣Инициализируйте счетчик для подсчета палиндромных подстрок.

2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.

3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.

😎 Решение:

function countSubstrings($s) {
    $totalCount = 0;

    function expandAroundCenter($s, $left, $right) {
        $count = 0;
        while ($left >= 0 && $right < strlen($s) && $s[$left] == $s[$right]) {
            $count++;
            $left--;
            $right++;
        }
        return $count;
    }

    for ($i = 0; $i < strlen($s); $i++) {
        $totalCount += expandAroundCenter($s, $i, $i);
        $totalCount += expandAroundCenter($s, $i, $i + 1);
    }

    return $totalCount;
}

Ставь 👍 и забирай 📚 Базу знаний