647. Palindromic Substrings

leetcode medium

#csharp#leetcode#medium#string#tree#two-pointers

Task

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

Пример:

Input: s = "abc"

Output: 3

C# solution

matched/original

public class Solution {
    public int CountSubstrings(string s) {
        int totalCount = 0;
        for (int i = 0; i < s.Length; i++) {
            totalCount += ExpandAroundCenter(s, i, i);
            totalCount += ExpandAroundCenter(s, i, i + 1);
        }
        return totalCount;
    }
    private int ExpandAroundCenter(string s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountSubstrings(string s) {
        int totalCount = 0;
        for (int i = 0; i < s.size(); i++) {
            totalCount += ExpandAroundCenter(s, i, i);
            totalCount += ExpandAroundCenter(s, i, i + 1);
        }
        return totalCount;
    }
    private int ExpandAroundCenter(string s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

Java solution

matched/original

public class Solution {
    public int countSubstrings(String s) {
        int totalCount = 0;
        for (int i = 0; i < s.length(); i++) {
            totalCount += expandAroundCenter(s, i, i);
            totalCount += expandAroundCenter(s, i, i + 1);
        }
        return totalCount;
    }

    private int expandAroundCenter(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

JavaScript solution

matched/original

var countSubstrings = function(s) {
    const expandAroundCenter = (left, right) => {
        let count = 0;
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    };

    let totalCount = 0;
    for (let i = 0; i < s.length; i++) {
        totalCount += expandAroundCenter(i, i);
        totalCount += expandAroundCenter(i, i + 1);
    }
    return totalCount;
};

Python solution

matched/original

def countSubstrings(s):
    def expandAroundCenter(left, right):
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count
    
    total_count = 0
    for i in range(len(s)):
        total_count += expandAroundCenter(i, i)  # For odd length palindromes
        total_count += expandAroundCenter(i, i + 1)  # For even length palindromes
    return total_count

Go solution

matched/original

package main

func expandAroundCenter(s string, left, right int) int {
    count := 0
    for left >= 0 && right < len(s) && s[left] == s[right] {
        count++
        left--
        right++
    }
    return count
}

func countSubstrings(s string) int {
    totalCount := 0
    for i := 0; i < len(s); i++ {
        totalCount += expandAroundCenter(s, i, i)
        totalCount += expandAroundCenter(s, i, i+1)
    }
    return totalCount
}

Explanation

Algorithm

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

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

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

😎